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

## What is the Weightage of Context Free Grammars and Push-down Automata in GATE Exam?

Total 26 Questions have been asked from Context Free Grammars and Push-down Automata topic of Theory of Computation subject in previous GATE papers. Average marks 1.65.

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

##### Show Answer

Which one of the following statements is FALSE?

##### Show Answer

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?

##### Show Answer

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

##### Show Answer

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}$

##### Show Answer

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?$

##### Show Answer

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?

##### Show Answer

Consider the transition diagram of a PDA given below with input alphabet and stack alphabet .Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is TRUE?

##### Show Answer

Consider the following languages:
$L_1=\{a^{n\;}b^{m\;}c^{n+m}:m,n\geq1\}$
$L_2=\{a^{n\;}b^{n\;}c^{2n}:,n\geq1\}$
Which one of the following is TRUE?

##### Show Answer

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,

int a[10][3];
The grammars use $D$ as the start symbol, and use six terminal symbols int ; id [ ] num.
 Grammar G1 Grammar G2 $D\rightarrow\mathbf{int}\boldsymbol\;L;$ $D\boldsymbol\rightarrow\mathbf{int}\boldsymbol\;L;$ $L\rightarrow\mathbf{id}\lbrack E$ $L\boldsymbol\rightarrow\mathbf{id}\boldsymbol\;E$ $E\rightarrow\mathbf{num}\rbrack$ $E\rightarrow E\lbrack\mathbf{num}\rbrack$ $E\rightarrow\mathbf{num}\rbrack\lbrack E$ $E\rightarrow\lbrack\mathbf{num}\rbrack$

Which of the grammars correctly generate the declaration mentioned above?

##### Show Answer

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

##### Show Answer

Which of the following languages are context-free?

L1 = {ambnanbm |m, n$\ge$1}
L2 = {ambnambn|m, n $\ge$1}
L3 = {ambn|m = 2n+1}

##### Show Answer

Consider the following languages.
${L}_{1}=\left\{{0}^{p}{1}^{q}{0}^{r}|p,q,r\ge 0\right\}$
${L}_{2}=\left\{{0}^{p}{1}^{q}{0}^{r}|p,q,r\ge 0,p\ne r\right\}$
Which one of the following statements is FALSE?

##### Show Answer

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)?

##### Show Answer

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

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

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

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

##### Show Answer

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?

##### Show Answer

Consider the languages L1 = {0i1j | ij}. L2 = {0i1j | i = j}. L3 = {0i1j | i = 2j + 1}. L4 = {0i1j | i ≠ 2j}. Which one of the following statements is true?

##### Show Answer

S → aSa|bSb|a|b

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

##### Show Answer

Which one of the following is FALSE?

##### Show Answer

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

 Group 1 Group 2 P. Regular expression 1. Syntax analysis Q. Pushdown automata 2. Code generation R. Dataflow analysis 3. Lexical analysis S. Register allocation 4. Code optimization

##### Show Answer

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

 Present State A Present State B Input Next State A Next State B Output 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 1

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?

##### Show Answer

Let L = L1$\cap$L2, where L1 and L2 are languages as defined below:

L1 = {am bm c an bn | m, n ≥ 0}
L2 = {ai bj ck | i, j, k ≥ 0}

Then L is

##### Show Answer

Which of the following statements is false?

##### Show Answer

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(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

##### Show Answer

Match the following:

 (E) Checking that identifiers are declared before their use (P)  $L=\left\{{a}^{n}{b}^{m}{c}^{n}{d}^{m}|n\ge 1,m\ge 1\right\}$ (F) Number of formal parameters in the declaration of a function agrees with the number of actual parameters in use of that function (Q) X $\to$X b X | X c X |  d X f | g (G) Arithmetic expressions with matched pairs of parentheses (R) L = {wcw|w$\in$(a|b)*} (H) Palindromes X $\to$ b X b | c X c | $\epsilon$

##### Show Answer

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