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?

L = { an bn |n ≥ 0} and is not accepted by any finite automata

L = { an | n ≥ 0} ∪ { anbn | n ≥ 0} and is not accepted by any deterministic PDA

L is not accepted by any Turing machine that halts on every input

L = { an|n ≥ 0} ∪ {anbn|n ≥ 0} and is deterministic context-free

Consider the following languages.L1 = {wxyx | w, x, y ϵ (0 + 1)+}L2 = {xy | x, y ϵ (a + b)*, |x| = |y|, x ≠ y}Which one of the following is TRUE?

L1 is context-free but not regular and L2 is context-free.

L1 is regular and L2 is context-free.

L1 is context-free but not regular and L2 is context-free.

Neither L1 nor L2 is context-free.

L1 is context-free but L2 is not context-free

Let L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context-free?

\(\overline {{{\bar L}_1} \cup {{\bar L}_2}} \)

Consider the following grammar.S → ABA → aA → BaBB → bbAWhich of the following statement is FALSE?

The length of every string produced by this grammar is even

No string produced by this grammar has three consecutive a's

The length of substring produced by B is always odd.

No string produced by this grammar has four consecutive b’s

Consider the following languages :L1 = {am bn | m ≠ n}L2 = {am bn | m = 2n + 1}L3 = {am bn | m ≠ 2n}Which one of the following statement is correct ?

Only L1 and L2 are context free languages

Only L1 and L3 are context free languages

Only L2 and L3 are context free languages

L1, L2 and L3 are context free languages

Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol:S → abScT | abcTT → bT | bWhich one of the following represents the language generated by the above grammar?

{(𝑎𝑏)𝑛 𝑐𝑏𝑚1 𝑐𝑏𝑚2 … 𝑐𝑏𝑚𝑛 |𝑛, 𝑚1, 𝑚2 … , 𝑚𝑛 ≥ 1}

Consider the following problems. L(

Only I, II and III are undecidable

Let \(\left\langle M \right\rangle \) denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?

L = { \(\left\langle M \right\rangle \) | M is a DFA such that L(M) = Φ}

L = { \(\left\langle M \right\rangle \) | M is a PDA such that L(M) = ∑*}

L = { \(\left\langle M \right\rangle \) | M is a DFA such that L(M) = Φ}

L = { \(\left\langle M \right\rangle \) | M is a PDA such that L(M) = Φ}

L = { \(\left\langle M \right\rangle \) | M is a DFA such that L(M) = ∑*}

Consider L = L1 ∩ L2Where L1 = {0m1m20n1n |m, n >= 0}L2 = {0m1n2k | m, n, k ≥ 0}Then, the language L is

Recursively enumerable but not context free

Consider the languages L1, L2 and L3 as given belowL1 = {0p1q | p, q ϵ N}L2 = {0p1q | p, q ϵ N and p = q} andL3 = {0p1q0r | p, q, r ϵ N and p = q r}Which of the following statements is NOT TRUE?

Turing machines can be used to recognize all the languages

Push Down Automata (PDA) can be used to recognize L1 and L2

All the three languages are context free

Turing machines can be used to recognize all the languages

Consider the following languages:L1 = {anbmcn + m: m, n ≥ 1}L2 = {anbnc2n: n ≥ 1}Which one of the following is TRUE?

L2 is context-free while L1 is not context-free

Both L1 and L2 are context-free

L1 is context-free while L2 is not context-free

L2 is context-free while L1 is not context-free

Neither L1 nor L2 is context-free

34 + Mcqs in Context Free Languages And Pushdown Automata in Computer Science Page 1 McqOptions

1.	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 recursiveII. L̅2 (complement of L2) is recursiveIII. L̅1 is context-freeIV. L̅1 ∪ L2 is recursively enumerable
A.	I only
B.	III only
C.	III and IV only
D.	I and IV only
Answer» E.

Discussion

2.	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?
A.	L = { an bn \|n ≥ 0} and is not accepted by any finite automata
B.	L = { an \| n ≥ 0} ∪ { anbn \| n ≥ 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 = { an\|n ≥ 0} ∪ {anbn\|n ≥ 0} and is deterministic context-free
Answer» E.

Discussion

3.	Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0,1}, Γ = {0,1,⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is set of states, Σ is the input alphabet, Γ is the stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states. The state transition is as follows:Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?
A.	10110
B.	10010
C.	01010
D.	01001
Answer» C. 01010

Discussion

4.	If G is a grammar with productionsS → SaS \| aSb \| bSa \| SS \| ∈Where S is the start variable. Then which one of the following strings in not generated by G?
A.	abab
B.	aaab
C.	abbaa
D.	babba
Answer» E.

Discussion

5.	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[ ] numGrammar G1Grammar G2D → int L;D → int L;L → id[EL → idEE → num]E → E[num]E → num][EE → [num] Which of the grammars correctly generate the declaration mentioned above?
A.	Both G1 and G2
B.	Only G1
C.	Only G2
D.	Neither G1 nor G2
Answer» B. Only G1

Discussion

6.	Consider the following languages.L1 = {wxyx \| w, x, y ϵ (0 + 1)+}L2 = {xy \| x, y ϵ (a + b)*, \|x\| = \|y\|, x ≠ y}Which one of the following is TRUE?
A.	L1 is regular and L2 is context-free.
B.	L1 is context-free but not regular and L2 is context-free.
C.	Neither L1 nor L2 is context-free.
D.	L1 is context-free but L2 is not context-free
Answer» B. L1 is context-free but not regular and L2 is context-free.

Discussion

7.	Let L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context-free?
A.	L1 ∩ L̅2
B.	L1 ∪ (L2 ∪ L̅2)
C.	\(\overline {{{\bar L}_1} \cup {{\bar L}_2}} \)
D.	(L1 ∩ L2) ∪ (L̅1 ∩ L2)
Answer» C. \(\overline {{{\bar L}_1} \cup {{\bar L}_2}} \)

Discussion

8.	A grammar that produces more than one left most derivation or right most derivation for the same sentence is known is _____.
A.	Non ambiguous
B.	Context sensitive
C.	Regular
D.	Ambiguous
Answer» E.

Discussion

9.	Consider the following grammar.S → ABA → aA → BaBB → bbAWhich of the following statement is FALSE?
A.	The length of every string produced by this grammar is even
B.	No string produced by this grammar has three consecutive a's
C.	The length of substring produced by B is always odd.
D.	No string produced by this grammar has four consecutive b’s
Answer» E.

Discussion

10.	Consider the following languages :L1 = {am bn \| m ≠ n}L2 = {am bn \| m = 2n + 1}L3 = {am bn \| m ≠ 2n}Which one of the following statement is correct ?
A.	Only L1 and L2 are context free languages
B.	Only L1 and L3 are context free languages
C.	Only L2 and L3 are context free languages
D.	L1, L2 and L3 are context free languages
Answer» E.

Discussion

11.	Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol:S → abScT \| abcTT → bT \| bWhich one of the following represents the language generated by the above grammar?
A.	{(ab)n (cb)n \| n ≥ 1}
B.	{(𝑎𝑏)𝑛 𝑐𝑏𝑚1 𝑐𝑏𝑚2 … 𝑐𝑏𝑚𝑛 \|𝑛, 𝑚1, 𝑚2 … , 𝑚𝑛 ≥ 1}
C.	{(ab)n (cbm)n \| m, n ≥ 1}
D.	{(ab)n (cbn)m \| m, n ≥ 1}
Answer» C. {(ab)n (cbm)n \| m, n ≥ 1}

Discussion

12.	Consider grammar G with productions A → a \| Aa \| bAA \| AAb \| AbAChoose a false statement :
A.	aaabb is in L(G)
B.	abb is in L(G)
C.	A is start symbol of G
D.	aaaabb is in L(G)
Answer» C. A is start symbol of G

Discussion

13.	Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable?I. Given a regular expression R and a string w, is w ∈ L(R)?II. Given a context-free grammar G, is L(G) = ϕ?III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑?IV. Given a Turing machine M and a string w, is w ∈ L(M)?
A.	I and IV only
B.	II and III only
C.	II, III and IV only
D.	III and IV only
Answer» E.

Discussion

14.	Consider the following problems. L(
A.	Only I and II are undecidable
B.	Only III is undecidable
C.	Only II and IV are undecidable
D.	Only I, II and III are undecidable
Answer» E.

Discussion

15.	Consider the following languagesL1 = {ap \| p is a prime number}L2 = {anbmc2m \| n ≥ 0, m ≥ 0}L3 = {anbnc2n \| n ≥ 0}L4 = {anbn \| n ≥ 1}Which of the following are CORRECT?I. L1 is context-free but not regular.II. L2 is not context-freeIII. L3 is not context-free but recursive.IV. L4 is deterministic context-free
A.	I, II and IV only
B.	II and III only
C.	I and IV only
D.	III and IV only
Answer» E.

Discussion

16.	CFG (Context Free Grammar) is not closed under
A.	Union
B.	Complementation
C.	Kleene star
D.	Product
Answer» C. Kleene star

Discussion

17.	Let \(\left\langle M \right\rangle \) denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?
A.	L = { \(\left\langle M \right\rangle \) \| M is a PDA such that L(M) = ∑*}
B.	L = { \(\left\langle M \right\rangle \) \| M is a DFA such that L(M) = Φ}
C.	L = { \(\left\langle M \right\rangle \) \| M is a PDA such that L(M) = Φ}
D.	L = { \(\left\langle M \right\rangle \) \| M is a DFA such that L(M) = ∑*}
Answer» B. L = { \(\left\langle M \right\rangle \) \| M is a DFA such that L(M) = Φ}

Discussion

18.	Consider the following languages over the alphabet Σ = {0,1, c}:L1 = {0n1n \| n ≥ 0}L2 = {wcwr \| w ϵ {0,1}}L3 = {wwr \| w ϵ {0,1}}Here, wr is the reverse of the string w. Which of these languages are deterministic Context-free languages?
A.	None of the languages
B.	Only L1
C.	Only L1 and L2
D.	All the three languages
Answer» D. All the three languages

Discussion

19.	Context free grammar is not closed under:
A.	Concatenation
B.	Complementation
C.	Kleene Star
D.	Union
Answer» C. Kleene Star

Discussion

20.	Consider the grammar with productionsS→ aSb\|SS\|ϵThis grammar is
A.	not context-free, not linear
B.	not context-free, linear
C.	context-free, not linear
D.	context free, linear
Answer» D. context free, linear

Discussion

21.	Context free languages are closed under
A.	union, intersection
B.	union, Kleene closure
C.	intersection, complement
D.	complement, Kleene closure
Answer» C. intersection, complement

Discussion

22.	Consider the language L = {an \|n ≥ 0} ∪ {anbn\| n ≥ 0} and the following statements.I. L is deterministic context-free.II. L is context-free but not deterministic context-free.III. L is not LL(k) for any k.Which of the above statements is/are TRUE?
A.	I only
B.	II only
C.	I and III only
D.	III only
Answer» D. III only

Discussion

23.	Let S be an NP-complete problem. Q and R are other two problems not known to be NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which of the following statements is true?
A.	R is NP-complete
B.	R is NP-hard
C.	Q is NP-complete
D.	Q is NP-hard
Answer» C. Q is NP-complete

Discussion

24.	Consider the following languages over the alphabet ∑ = {a, b, c}Let L1 = {an bn cm \| m, n ≥ 0} and L2 = {am bn cn \| m, n ≥ 0}Which of the following are context-free languages?I. L1 ∪ L2 II. L1 ∩ L2
A.	I only
B.	II only
C.	I and II
D.	Neither I nor II
Answer» B. II only

Discussion

25.	A CFG(Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A -> BC or A -> a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is
A.	2x-1
B.	2x
C.	2x+1
D.	2x
Answer» B. 2x

Discussion

26.	Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?I. L1 ∪ L2 is context-freeII. L̅1 is context-freeIII. L1 – R is context-freeIV. L1 ∩ L2 is context-free
A.	I, II and IV only
B.	I and III only
C.	II and IV only
D.	I only
Answer» C. II and IV only

Discussion

27.	Consider the following languages:I. \(
A.	I and IV only
B.	I and II only
C.	II and III only
D.	II and IV only
Answer» C. II and III only

Discussion

28.	Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.G1: S → aSb \| T, T → cT \| ∈G2: S → bSa \| T, T → cT \| ∈The language L(G1) ∩ L(G2) is
A.	Finite
B.	Not finite but regular
C.	Context-Free but not regular
D.	Recursive but not context-free
Answer» C. Context-Free but not regular

Discussion

29.	Identify the language generated by the following grammarS → ABA → aAb\|ϵB → bB\|b
A.	{ambn\|n ≥ m, m > 0}
B.	{ambn\|n > m, m ≥ 0}
C.	{ambn\|n > m, m > 0}
D.	{ambn\|n ≥ m, m ≥ 0}
Answer» C. {ambn\|n > m, m > 0}

Discussion

30.	Consider L = L1 ∩ L2Where L1 = {0m1m20n1n \|m, n >= 0}L2 = {0m1n2k \| m, n, k ≥ 0}Then, the language L is
A.	Recursively enumerable but not context free
B.	Regular
C.	Context free but not regular
D.	Not recursive
Answer» D. Not recursive

Discussion

31.	Consider the languages L1, L2 and L3 as given belowL1 = {0p1q \| p, q ϵ N}L2 = {0p1q \| p, q ϵ N and p = q} andL3 = {0p1q0r \| p, q, r ϵ N and p = q r}Which 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
Answer» D. Turing machines can be used to recognize all the languages

Discussion

32.	For a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR = 10110.Which of the following languages is/are context-free?
A.	{wxxRwR \| w, x ∈ {0, 1}*}
B.	{wxwR \| w, x ∈ {0, 1}*}
C.	{wxwRxR \| w, x ∈ {0, 1}*}
D.	{wwRxxR \| w, x ∈ {0, 1}*}
Answer» B. {wxwR \| w, x ∈ {0, 1}*}

Discussion

33.	Consider the following languages:L1 = {anbmcn + m: m, n ≥ 1}L2 = {anbnc2n: n ≥ 1}Which one of the following is TRUE?
A.	Both L1 and L2 are context-free
B.	L1 is context-free while L2 is not context-free
C.	L2 is context-free while L1 is not context-free
D.	Neither L1 nor L2 is context-free
Answer» C. L2 is context-free while L1 is not context-free

Discussion

34.	Consider the following types of languages: L1: Regular, L2: Context-free, L3 : Recursive, L4 : Recursively enumerable. Which of the following is/are TRUE?I. L̅3 ∪ L4 is recursively enumerableII. L̅2 ∪ L3 is recursiveIII. L1* ∩ L2 is context-free IV. L1 ∪ L̅2 is context-free
A.	I only
B.	I and III only
C.	I and IV only
D.	I, II and III only
Answer» E.

Discussion

29.	Identify the language generated by the following grammarS → ABA → aAb\|ϵB → bB\|b
A.	{ambn\|n ≥ m, m > 0}
B.	{ambn\|n > m, m ≥ 0}
C.	{ambn\|n > m, m > 0}
D.	{ambn\|n ≥ m, m ≥ 0}
Answer» C. {ambn\|n > m, m > 0}

Explore topic-wise MCQs in Computer Science.

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?

If G is a grammar with productionsS → SaS | aSb | bSa | SS | ∈Where S is the start variable. Then which one of the following strings in not generated by G?

Consider the following languages.L1 = {wxyx | w, x, y ϵ (0 + 1)+}L2 = {xy | x, y ϵ (a + b)*, |x| = |y|, x ≠ y}Which one of the following is TRUE?

Let L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context-free?

A grammar that produces more than one left most derivation or right most derivation for the same sentence is known is _____.

Consider the following grammar.S → ABA → aA → BaBB → bbAWhich of the following statement is FALSE?

Consider the following languages :L1 = {am bn | m ≠ n}L2 = {am bn | m = 2n + 1}L3 = {am bn | m ≠ 2n}Which one of the following statement is correct ?

Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol:S → abScT | abcTT → bT | bWhich one of the following represents the language generated by the above grammar?

Consider grammar G with productions A → a | Aa | bAA | AAb | AbAChoose a false statement :

Consider the following problems. L(

CFG (Context Free Grammar) is not closed under

Let \(\left\langle M \right\rangle \) denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?

Consider the following languages over the alphabet Σ = {0,1, c}:L1 = {0n1n | n ≥ 0}L2 = {wcwr | w ϵ {0,1}}L3 = {wwr | w ϵ {0,1}}Here, wr is the reverse of the string w. Which of these languages are deterministic Context-free languages?

Context free grammar is not closed under:

Consider the grammar with productionsS→ aSb|SS|ϵThis grammar is

Context free languages are closed under

Consider the language L = {an |n ≥ 0} ∪ {anbn| n ≥ 0} and the following statements.I. L is deterministic context-free.II. L is context-free but not deterministic context-free.III. L is not LL(k) for any k.Which of the above statements is/are TRUE?

Let S be an NP-complete problem. Q and R are other two problems not known to be NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which of the following statements is true?

Consider the following languages over the alphabet ∑ = {a, b, c}Let L1 = {an bn cm | m, n ≥ 0} and L2 = {am bn cn | m, n ≥ 0}Which of the following are context-free languages?I. L1 ∪ L2 II. L1 ∩ L2

A CFG(Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A -> BC or A -> a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?I. L1 ∪ L2 is context-freeII. L̅1 is context-freeIII. L1 – R is context-freeIV. L1 ∩ L2 is context-free

Consider the following languages:I. \(

Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.G1: S → aSb | T, T → cT | ∈G2: S → bSa | T, T → cT | ∈The language L(G1) ∩ L(G2) is

Identify the language generated by the following grammarS → ABA → aAb|ϵB → bB|b

Consider L = L1 ∩ L2Where L1 = {0m1m20n1n |m, n >= 0}L2 = {0m1n2k | m, n, k ≥ 0}Then, the language L is

Consider the languages L1, L2 and L3 as given belowL1 = {0p1q | p, q ϵ N}L2 = {0p1q | p, q ϵ N and p = q} andL3 = {0p1q0r | p, q, r ϵ N and p = q r}Which of the following statements is NOT TRUE?

For a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR = 10110.Which of the following languages is/are context-free?

Consider the following languages:L1 = {anbmcn + m: m, n ≥ 1}L2 = {anbnc2n: n ≥ 1}Which one of the following is TRUE?

Consider the following types of languages: L1: Regular, L2: Context-free, L3 : Recursive, L4 : Recursively enumerable. Which of the following is/are TRUE?I. L̅3 ∪ L4 is recursively enumerableII. L̅2 ∪ L3 is recursiveIII. L1* ∩ L2 is context-free IV. L1 ∪ L̅2 is context-free

Explore topic-wise MCQs in Computer Science.

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?

If G is a grammar with productionsS → SaS | aSb | bSa | SS | ∈Where S is the start variable. Then which one of the following strings in not generated by G?

Consider the following languages.L1 = {wxyx | w, x, y ϵ (0 + 1)+}L2 = {xy | x, y ϵ (a + b)*, |x| = |y|, x ≠ y}Which one of the following is TRUE?

Let L1 be a regular language and L2 be a context-free language. Which of the following languages is/are context-free?

A grammar that produces more than one left most derivation or right most derivation for the same sentence is known is _____.

Consider the following grammar.S → ABA → aA → BaBB → bbAWhich of the following statement is FALSE?

Consider the following languages :L1 = {am bn | m ≠ n}L2 = {am bn | m = 2n + 1}L3 = {am bn | m ≠ 2n}Which one of the following statement is correct ?

Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol:S → abScT | abcTT → bT | bWhich one of the following represents the language generated by the above grammar?

Consider grammar G with productions A → a | Aa | bAA | AAb | AbAChoose a false statement :

Consider the following problems. L(

CFG (Context Free Grammar) is not closed under

Let \(\left\langle M \right\rangle \) denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?

Consider the following languages over the alphabet Σ = {0,1, c}:L1 = {0n1n | n ≥ 0}L2 = {wcwr | w ϵ {0,1}*}L3 = {wwr | w ϵ {0,1}*}Here, w­r is the reverse of the string w. Which of these languages are deterministic Context-free languages?

Context free grammar is not closed under:

Consider the grammar with productionsS→ aSb|SS|ϵThis grammar is

Context free languages are closed under

Consider the language L = {an |n ≥ 0} ∪ {anbn| n ≥ 0} and the following statements.I. L is deterministic context-free.II. L is context-free but not deterministic context-free.III. L is not LL(k) for any k.Which of the above statements is/are TRUE?

Let S be an NP-complete problem. Q and R are other two problems not known to be NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which of the following statements is true?

Consider the following languages over the alphabet ∑ = {a, b, c}Let L1 = {an bn cm | m, n ≥ 0} and L2 = {am bn cn | m, n ≥ 0}Which of the following are context-free languages?I. L1 ∪ L2 II. L1 ∩ L2

A CFG(Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A -> BC or A -> a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT?I. L1 ∪ L2 is context-freeII. L̅1 is context-freeIII. L1 – R is context-freeIV. L1 ∩ L2 is context-free

Consider the following languages:I. \(

Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.G1: S → aSb | T, T → cT | ∈G2: S → bSa | T, T → cT | ∈The language L(G1) ∩ L(G2) is

Identify the language generated by the following grammarS → ABA → aAb|ϵB → bB|b

Consider L = L1 ∩ L2Where L1 = {0m1m20n1n |m, n >= 0}L2 = {0m1n2k | m, n, k ≥ 0}Then, the language L is

Consider the languages L1, L2 and L3 as given belowL1 = {0p1q | p, q ϵ N}L2 = {0p1q | p, q ϵ N and p = q} andL3 = {0p1q0r | p, q, r ϵ N and p = q r}Which of the following statements is NOT TRUE?

For a string w, we define wR to be the reverse of w. For example, if w = 01101 then wR = 10110.Which of the following languages is/are context-free?

Consider the following languages:L1 = {anbmcn + m: m, n ≥ 1}L2 = {anbnc2n: n ≥ 1}Which one of the following is TRUE?

Consider the following types of languages: L1: Regular, L2: Context-free, L3 : Recursive, L4 : Recursively enumerable. Which of the following is/are TRUE?I. L̅3 ∪ L4 is recursively enumerableII. L̅2 ∪ L3 is recursiveIII. L1* ∩ L2 is context-free IV. L1 ∪ L̅2 is context-free

Consider the following languages over the alphabet Σ = {0,1, c}:L1 = {0n1n | n ≥ 0}L2 = {wcwr | w ϵ {0,1}}L3 = {wwr | w ϵ {0,1}}Here, wr is the reverse of the string w. Which of these languages are deterministic Context-free languages?