Automata qn 2 - Revision history

Arjun Suresh at 11:25, 15 July 2014

2014-07-15T11:25:06Z

2014-07-14T09:25:02Z

2014-07-13T22:39:04Z

2014-07-07T09:42:41Z

2014-06-03T16:39:50Z

2014-04-14T14:05:58Z

2013-12-18T22:26:33Z

2013-12-18T22:24:52Z

2013-12-18T22:24:10Z

2013-12-18T22:23:51Z

← Older revision		Revision as of 11:25, 15 July 2014
Line 23:		Line 23:
	{{Template:FBD}}		{{Template:FBD}}

−
−	~~[[Category: Automata questions]]~~
	[[Category: Non-GATE Questions from Automata Theory]]		[[Category: Non-GATE Questions from Automata Theory]]

← Older revision		Revision as of 09:25, 14 July 2014
Line 25:		Line 25:

	[[Category: Automata questions]]		[[Category: Automata questions]]
−	[[Category: Non-GATE Questions]]	+	[[Category: Non-GATE Questions from Automata Theory]]

← Older revision		Revision as of 22:39, 13 July 2014
Line 25:		Line 25:

	[[Category: Automata questions]]		[[Category: Automata questions]]
−	[[Category: Questions]]	+	[[Category: Non-GATE Questions]]

@@ Line 23: / Line 23: @@
 {{Template:FBD}}
-[[Category:Automata Theory]]
 [[Category: Automata questions]]
 [[Category: Questions]]

← Older revision		Revision as of 16:39, 3 June 2014
Line 24:		Line 24:

	[[Category:Automata Theory]]		[[Category:Automata Theory]]
		+	[[Category: Automata questions]]
	[[Category: Questions]]		[[Category: Questions]]

@@ Line 15: / Line 15: @@
 (D) None of the above
-===Solution===
+==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
    $L_1$ is clearly a DCFL. And DCFL is closed under complement. Hence, $L_2$ is also DCFL.

← Older revision		Revision as of 22:26, 18 December 2013
Line 19:		Line 19:

	We can make a PDA for L₂ , using the same PDA for {aⁿbⁿ} as follows:		We can make a PDA for L₂ , using the same PDA for {aⁿbⁿ} as follows:
−	Start by pushing each a on to stack. When b comes start popping. If 'a' comes after a 'b' or 'b' comes when the stack is empty, go to a ~~new~~ state from where the PDA accepts any string~~. (make it the final state and accepts everything else in the string)~~. Otherwise, at the end of the string, if stack is non-empty, accept the string	+	Start by pushing each 'a' on to stack. When b comes start popping. If 'a' comes after a 'b' or 'b' comes when the stack is empty, go to a final state from where the PDA accepts any string. Otherwise, at the end of the string, if stack is non-empty, accept the string and if stack is empty, reject the string.
		+
		+	{{Template:FBD}}
		+
		+	[[Category:Automata Theory]]
		+	[[Category: Questions]]

@@ Line 18: / Line 18: @@
    $L_1$ is clearly a DCFL. And DCFL is closed under complement. Hence, $L_2$ is also DCFL.
- We can make a PDA for L₂ , using the same PDA for {aⁿbⁿ}.
+We can make a PDA for L₂ , using the same PDA for {aⁿbⁿ} as follows:
-Start by pushing each a on to stack. When b comes start popping. If 'a' comes after a 'b' or 'b' comes when the stack is empty, go to a new state from where the PDA accepts any string. (make it the final state and accepts everything else in the string). Otherwise, at the end of the string, if stack is non-empty, accept the string
+ Start by pushing each a on to stack. When b comes start popping. If 'a' comes after a 'b' or 'b' comes when the stack is empty, go to a new state from where the PDA accepts any string. (make it the final state and accepts everything else in the string). Otherwise, at the end of the string, if stack is non-empty, accept the string

@@ Line 1: / Line 1: @@
 Consider the following languages
-$L_1 = {a^nb^n| n \ge 0\}$
+$L_1 = \{a^nb^n| n \ge 0\}$
 $L_2 =$ Complement($L_1$)