TestMagic

Jeffrey.fu · 2009 October 16th, 06:05 AM

In some CS-notes downloaded here It says that " an interesting note is that if a machine (finite automata, deterministic or non-deterministic, etc.) can recognize a language, the same type of machine can recognize the complement of the language by switching accept and reverse states."

But, I think that's not right. For instance, if L is CFL, then the complement of L may not be CFL.

CalmLogic · 2009 October 17th, 04:53 PM

Quote:

But, I think that's not right.

They aren't talking about a CFL, though.

Jeffrey.fu · 2009 October 18th, 01:34 PM

Thanks, it's my misunderstanding.

Enigma211 · 2009 October 18th, 07:08 PM

This is for Regular languages.

2009 October 16th, 06:05 AM	#1 (permalink)
Jeffrey.fu I JUST got here. Join Date: Jun 2009 Posts: 4	complement of some language In some CS-notes downloaded here It says that " an interesting note is that if a machine (finite automata, deterministic or non-deterministic, etc.) can recognize a language, the same type of machine can recognize the complement of the language by switching accept and reverse states." But, I think that's not right. For instance, if L is CFL, then the complement of L may not be CFL.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

2009 October 18th, 01:34 PM	#3 (permalink)
Jeffrey.fu I JUST got here. Join Date: Jun 2009 Posts: 4	Thanks, it's my misunderstanding.

2009 October 18th, 07:08 PM	#4 (permalink)
Enigma211 Eager! Join Date: May 2008 Posts: 39	This is for Regular languages.

TestMagic

Free GMAT, GRE, SAT Test, TOEFL practice tests