GATE Questions & Answers of Context Free Grammars and Push-down Automata

Which one of the following languages over $ \sum\;=\;\{a,\;b\} $ is NOT context-free?

•  (A)  $ \{ww^R\vert w\in\{a,\;b\}^\ast\} $
•  (B)  $ \{wa^nb^nw^R\vert w\in\{a,\;b\}^\ast,\;n\geq0\} $
•  (C)  $ \{wa^nw^Rb^n\vert w\in\{a,\;b\}^\ast,\;n\geq0\} $
•  (D)  $ \{a^nb^i\vert i\in\{n,\;3n,\;5n\},\;n\geq0\} $

Which one of the following statements is FALSE?

•  (A)  Context-free grammar can be used to specify both lexical and syntax rules.
•  (B)  Type checking is done before parsing.
•  (C)  High-level language programs can be translated to different Intermediate Representations.
•  (D)  Arguments to a function can be passed using the program stack.

Consider the following context-free grammar over the alphabet $\style{font-family:'Times New Roman'}{\sum=\{a,b,c\}}$ with S as the  start  symbol:

$\style{font-family:'Times New Roman'}{\begin{array}{l}S\rightarrow abScT\;\vert\;abcT\\T\rightarrow bT\;\vert\;b\end{array}}$

Which one of the following represents the language genrated by the above grammar?

•  (A)  $\style{font-family:'Times New Roman'}{\{(ab)^n(cb)^n\vert n\geq1\}}$
•  (B)  $\style{font-family:'Times New Roman'}{\{(ab)^ncb^{m_1}cb^{m_2}.....cb^{m_n}\vert n,m_1,m_2,....m_n\geq1\}}$
•  (C)  $\style{font-family:'Times New Roman'}{\{(ab)^n\left(cb^m\right)^n\vert m,n\geq1\}}$
•  (D)  $\style{font-family:'Times New Roman'}{\{(ab)^n\left(cb^n\right)^m\vert m,n\geq1\}}$

Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are non-terminals.

$\style{font-family:'Times New Roman'}{\begin{array}{l}G_1:S\rightarrow\;aSb\vert T,T\rightarrow cT\vert\in\\G_2:S\rightarrow bSa\vert T,T\rightarrow cT\vert\in\end{array}}$

The language $\style{font-family:'Times New Roman'}{L(G_{1\;})\;\cap\;L(G_2)}$ is

•  (A)  Finite
•  (B)  Not finite but regular.
•  (C)  Context-Free but not regular
•  (D)  Recursive but not context-free

Identify the language genrated by the following grammar, where S is the start variable

$\begin{array}{l}S\rightarrow XY\\X\rightarrow aX\;\vert a\\Y\rightarrow aYb\;\vert\in\end{array}$

•  (A)  $ \{a^mb^n\vert m\geq n,\;n>0\} $
•  (B)  $\{a^mb^n\vert m\geq n,\;n\geq0\}$
•  (C)  $\style{font-family:'Times New Roman'}{\{a^mb^n\vert m>n,\;n\geq0\}}$
•  (D)  $\style{font-family:'Times New Roman'}{\{a^mb^n\vert m>n,\;n>0\}}$

Which of the following decision problems are undecidable?

I. Given NFAs $N_1$ and $N_2$, is $L$($N_1$)∩$L$($N_2$) =$\mathrm\Phi?$

II. Given a CFG G = $(N,Σ,P,S)$ and a string $x\in\Sigma^\ast$, does $x\in L\ast\left(G\right)?$

III. Given CFGs $G_1$ and $G_2$, is $L$($G_1$) = $L$($G_2$)?

IV. Given a TM $M$, is $L\left(M\right)=\mathrm\Phi?$

•  (A)  I and IV only
•  (B)  II and III only
•  (C)  III and IV only
•  (D)  II and IV only

Consider the following context-free grammars:

$G_1:\;S\rightarrow aS\vert B,B\rightarrow b\vert bB$
$G_2:\;S\rightarrow aA\vert bB,A\rightarrow aA\vert B\vert\varepsilon,B\rightarrow bB\vert\varepsilon$

Which one of the following pairs of languages is generated by $G_1$ and $G_2$, respectively?

•  (A)  $\{a^mb^n\vert m>0\;\mathrm{or}\;n>0\}\mathrm{and}\{a^mb^n\vert m>0\;\mathrm{and}\;n>0\}$
•  (B)  $\{a^mb^n\vert m>0\;\mathrm{and}\;n>0\}\mathrm{and}\{a^mb^n\vert m>0\;\mathrm{or}\;n\geq0\}$
•  (C)  $\{a^mb^n\vert m\geq0\;\mathrm{or}\;n>0\}\mathrm{and}\{a^mb^n\vert m>0\;\mathrm{and}\;n>0\}$
•  (D)  $\{a^mb^n\vert m\geq0\;\mathrm{and}\;n>0\}\mathrm{and}\{a^mb^n\vert m>0\;\mathrm{or}\;n>0\}$

Consider the transition diagram of a PDA given below with input alphabet $\Sigma = \{a,b\}$ and stack alphabet $\mathrm{\Gamma } =\{X,Z\}$ .Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is TRUE?

•  (A)  $L =\left\{a^n{b}^n\right|n\ge 0\}$ and is not accepted by any finite automata 
•  (B)  $L =\left\{a^n\right|n\ge 0\}\cup \{a^n{b}^n|n\ge 0\}$ and is not accepted by any deterministic PDA
•  (C)  $L$ is not accepted by any Turing machine that halts on every input
•  (D)  $L =\left\{a^n\right|n\ge 0\}\cup \{a^n{b}^n|n\ge 0\}$ and is deterministic context-free

•  (A)  Both $L_1$ and $L_2$ are context-free.
•  (B)  $L_1$ is context-free while $L_2$ is not context-free.
•  (C)  $L_2$ is context-free while $L_1$ is not context-free.
•  (D)  Neither $L_1$ nor $ L_2$ is context-free.

A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example,

•  (A)  Both G1 and G2
•  (B)  Only G1
•  (C)  Only G2
•  (D)  Neither G1 nor G2

For any two languages L₁ and L₂ such that L₁ is context-free and L₂ is recursively enumerable but not recursive, which of the following is/are necessarily true?
I. ${\overline{L}}_1$ (complement of L₁) is recursive
II. ${\overline{L}}_2$ (complement of L₂) is recursive
III. ${\overline{L}}_1$ is context – free
IV. ${\overline{L}}_1\cup L_2$ is recursively enumerable

•  (A)  I
•  (B)  III
•  (C)  III and IV
•  (D)  I and IV

Which of the following languages are context-free?

L₁ = {a^mbⁿaⁿb^m |m, n$\ge$1}
L₂ = {a^mbⁿa^mbⁿ|m, n $\ge$1}
L₃ = {a^mbⁿ|m = 2n+1}

•  (A)   L₁ and L₂ only
•  (B)   L₁and L₃ only
•  (C)   L₂ and L₃ only
•  (D)   L₃ only

Consider the following languages.
$L_1=\{0^p{1}^q{0}^r|<!--\; |\; -->p,q,r\ge <!--\; =\; -->0\}$
$L_2=\{0^p{1}^q{0}^r|<!--\; |\; -->p,q,r\ge <!--\; =\; -->0,p\ne <!--\; ?\; -->r\}$
Which one of the following statements is FALSE?

•  (A) L₂ is context-free.
•  (B) L₁∩ L₂ is context-free.
•  (C) Complement of L₂ is recursive.
•  (D) Complement of L₁ is context-free but not regular.

Which of the following is/are undecidable?
1. G is a CFG. Is L(G) = Φ?
2. G is a CFG. Is L(G) = Σ*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?

•  (A) 3 only
•  (B) 3 and 4 only
•  (C) 1, 2 and 3 only
•  (D) 2 and 3 only

Consider the languages L1. L2 and L3 as given below.

L1= {0^p 1^q |  p , q ∈ N },

L2= {0  ^p   1  ^q   |   p  ,  q  ∈ N  and  p  = q} and 

L3 = {0^p 1^q 0^r |   p  ,  q , r   ∈ N and   p   =  q  = r}. W h ich of the following statements is NOT TRUE?

•  (A) Push Down Automata (PDA) can be used to recognize L1 and L2
•  (B) L1 is a regular language
•  (C) All the three languages are context free
•  (D) Turing machines can be used to recognize all the languages

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

•  (A) $\mathrm{L}2-\mathrm{L}1$ is recursively enumerable
•  (B) $\mathrm{L}1-\mathrm{L}3$ is recursively enumerable
•  (C) $\mathrm{L}2\cap \mathrm{L}3$ is recursively enumerable
•  (D) $\mathrm{L}2\cup \mathrm{L}3$ is recursively enumerable

Consider the languages L1 = {0  ⁱ  1  ^j   |   i   ≠  j }.  L 2  = {0 ⁱ 1 ^j  |  i  = j}. L 3 = {0 ⁱ 1 ^j  |  i   = 2j + 1 }. L4 = {0 ⁱ1^j | i ≠ 2j}. Which one of the following statements is true?

•  (A) Only L2 is context free
•  (B) Only L2 and L3 are context free
•  (C) Only L1 and L2 are context free
•  (D) All are context free

S → aSa|bSb|a|b

The language generated by the above grammar over the alphabet {a,b} is the set of

•  (A) all palindromes.
•  (B) all odd length palindromes.
•  (C) strings that begin and end with the same symbol.
•  (D) all even length palindromes.

Which one of the following is FALSE?

•  (A) There is unique minimal DFA for every regular language.
•  (B) Every NFA can be converted to an equivalent PDA.
•  (C) Complement of every context-free language is recursive.
•  (D) Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

Match all items in Group 1 with correct options from those given in Group 2.

•  (A) P-4. Q-1, R-2, S-3
•  (B) P-3, Q-1, R-4, S-2
•  (C) P-3, Q-4, R-1, S-2
•  (D) P-2, Q-1, R-4, S-3

Given the following state table of an FSM with two states A and B, one input and one output:

If the initial state is A = 0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output=1?

•  (A) 3
•  (B) 4
•  (C) 5
•  (D) 6

Let L = L₁$\cap$L₂, where L₁ and L₂ are languages as defined below:

 L₁ = {a^m b^m c aⁿ bⁿ | m, n ≥ 0}
 L₂ = {aⁱ b^j c^k | i, j, k ≥ 0}

Then L is

•  (A) Not recursive
•  (B) Regular
•  (C) Context free but not regular
•  (D) Recursively enumerable but not context free.

Which of the following statements is false?

•  (A) Every NFA can be converted to an equivalent DFA
•  (B) Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
•  (C) Every regular language is also a context-free language
•  (D) Every subset of a recursively enumerable set is recursive

Which of the following statements are true?
I. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa
II. All $\epsilon$-productions can be removed from any context-free grammar by suitable transformations
III. The language generated by a context-free grammar all of whose productions are of the form$\mathrm{ \; X}\to w or X\to wY$(where, w is a string of terminals and Y is a non-terminal), is always regular
IV. The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees

•  (A)  I, II, III and IV
•  (B) II, III and IV only
•  (C)  I, III and IV only
•  (D)  I, II and IV only

Match the following:

•  (A) E -P, F -R, G -Q, H-S
•  (B) E -R, F -P, G -S, H -Q
•  (C) E -R, F-P, G -Q, H-S
•  (D) E -P, F -R, G-S, H -Q

The language L = {0ⁱ21ⁱ | i ≥ 0} over the alphabet {0, 1, 2} is:

•  (A) not recursive
•  (B) is recursive and is a deterministic CFL
•  (C) is a regular language
•  (D) is not a deterministic CFL but a CFL