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

Which one of the following statements is FALSE?

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?

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

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

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

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?

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?

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?

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?

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

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}

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?

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

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?

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?

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?

S → aSa|bSb|a|b

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

Which one of the following is FALSE?

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

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?

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

Which of the following statements is false?

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

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