Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| 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 | + | 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]] | ||
Consider the following languages
$L_1 = \{a^nb^n| n \ge 0\}$
$L_2 =$ Complement($L_1$)
Chose the appropriate option regarding the languages $L_1$ and $L_2$
(A) $L_1$ and $L_2$ are context free
(B) $L_1$ is context free but $L_2$ is regular
(C) $L_1$ is context free and $L_2$ is context sensitive
(D) None of the above
$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ⁿ} 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 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.
Consider the following languages
$L_1 = \{a^nb^n| n \ge 0\}$
$L_2 =$ Complement($L_1$)
Chose the appropriate option regarding the languages $L_1$ and $L_2$
(A) $L_1$ and $L_2$ are context free
(B) $L_1$ is context free but $L_2$ is regular
(C) $L_1$ is context free and $L_2$ is context sensitive
(D) None of the above
$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ⁿ} 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 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.
GATECSE