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

Question No. 10

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?

Question No. 37

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

Question No. 116

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

Question No. 27

Which of the following decision problems are undecidable?

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

II. Given a CFG G = (N,Σ,P,S) and a string x∈Σ, does x∈L(G)?

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

IV. Given a TM M, is L(M) =Φ?

Question No. 52

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?

Question No. 53

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

Which one of the following is TRUE?

Question No. 153

Consider the following languages:
Which one of the following is TRUE?

Question No. 156

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\boldsymbol\rightarrow\boldsymbol i\boldsymbol n\boldsymbol t\boldsymbol\;\boldsymbol L\boldsymbol;$ $D\boldsymbol\rightarrow\boldsymbol i\boldsymbol n\boldsymbol t\boldsymbol\;\boldsymbol L\boldsymbol;$
$\boldsymbol L\boldsymbol\rightarrow\boldsymbol i\boldsymbol d\lbrack E$ $\boldsymbol L\boldsymbol\rightarrow\boldsymbol i\boldsymbol d\boldsymbol\;E$
$E\rightarrow\mathrm{num}\rbrack$ $E\rightarrow E\lbrack\mathrm{num}\rbrack$
$E\rightarrow\mathrm{num}\rbrack\lbrack\mathrm E$ $E\rightarrow\lbrack\mathrm{num}\rbrack$


Which of the grammars correctly generate the declaration mentioned above?

Question No. 28

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. L¯1 (complement of L1) is recursive
II. L¯2 (complement of L2) is recursive
III. L¯1 is context – free
IV. L¯1L2 is recursively enumerable

Question No. 244

Which of the following languages are context-free?

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

Question No. 32

Consider the following languages.
L 1 = { 0 p 1 q 0 r | p , q , r 0 }
L 2 = { 0 p 1 q 0 r | p , q , r 0 , p r }
Which one of the following statements is FALSE?

Question No. 41

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

Question No. 26

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?

Question No. 17

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?

Question No. 40

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?

Question No. 12

S → aSa|bSb|a|b

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

Question No. 16

Which one of the following is FALSE?

Question No. 17

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

Question No. 27

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?

Question No. 40

Let L = L1L2, 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

Question No. 48

Which of the following statements is false?

Question No. 50

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 ε-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  Xw or XwY(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

Question No. 51

Match the following:

(E) Checking that identifiers are declared before their use (P)  L=anbmcndm|n1,m1

(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 X b X | X c X |  d X f | g
(G) Arithmetic expressions with matched pairs of parentheses (R) L = {wcw|w(a|b)*}
(H) Palindromes X b X b | c X c | ε

Question No. 30

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