Context Free Languages and Pushdown Automata MCQ Quiz - Objective Question with Answer for Context Free Languages and Pushdown Automata - Download Free PDF

Last updated on Apr 11, 2025

Latest Context Free Languages and Pushdown Automata MCQ Objective Questions

Context Free Languages and Pushdown Automata Question 1:

Let L = L1 ∩ L2 where L1 and L2 are language defined below :

L1 = {ambmc an bn m, n ≥ 0}

L2 = {aibj ck | i, j, k ≥ 0}

Then L is : 

  1. Not Recursive
  2. Regular 
  3. Context Free but not regular 
  4. Recursively enumerable but not context free

Answer (Detailed Solution Below)

Option 1 : Not Recursive

Context Free Languages and Pushdown Automata Question 1 Detailed Solution

The correct answer is Not Recursive.

key-point-imageKey Points

  • Let L = L1 ∩ L2 where L1 and L2 are languages defined below :
    • L1 = {ambmcanbn | m, n ≥ 0}
    • L2 = {aibjck | i, j, k ≥ 0}
  • The intersection of these two languages is a language L where the number of a's is equal to the number of b's and the number of c's is equal to the number of b's.
  • This language is not recursive because it cannot be decided by a Turing machine in a finite amount of time.

additional-information-imageAdditional Information

  • A recursive language is a type of formal language that can be decided by a Turing machine that always halts.
  • A language is considered recursively enumerable if there is a Turing machine that will halt and accept the strings in the language but may run forever for strings not in the language.
  • Regular languages can be recognized by finite automata and are a subset of context-free languages.
  • Context-free languages can be recognized by pushdown automata and include most programming languages.

Context Free Languages and Pushdown Automata Question 2:

Consider the grammar with nonterminals N = {S, C, S1} terminals T = {a, b, i, t, e} With S as the start symbol , and the following set of rules :

S → i Ct SS1|a

S1 → es | ∈

C → b

The grammar is not LL(1) because : 

  1. It is left recursive
  2. It is right recursive 
  3. It is ambiguous
  4. It is not context free

Answer (Detailed Solution Below)

Option 1 : It is left recursive

Context Free Languages and Pushdown Automata Question 2 Detailed Solution

The correct answer is It is left recursive.

Key Points

  • The grammar is not LL(1) because it is left recursive.
  • Left recursion in a grammar occurs when a non-terminal appears as the first symbol on the right-hand side of its own production.
  • In this grammar, the production rule S → i Ct SS1 indicates that the non-terminal S is left recursive.
  • Due to this left recursion, it is not possible to construct a predictive parser (such as an LL(1) parser) since it relies on the first symbol of the production.
  • An LL(1) parser requires that the first symbol of each production is unique to make a decision, which is not possible in the presence of left recursion.

Additional Information

  • To convert this grammar to an LL(1) grammar, left recursion must be eliminated.
  • This can be achieved by transforming the grammar into an equivalent one without left recursion.
  • For example, the production S → i Ct SS1 | a can be transformed by introducing new non-terminals and adjusting the rules accordingly.
  • Eliminating left recursion ensures that the parser can make decisions based on the first symbol of the production, making it suitable for LL(1) parsing.

Context Free Languages and Pushdown Automata Question 3:

Which of the following represents the output of the transition function(δ)

δ(q0,a) = (q1, x, R)

δ(q1,a) = (q1, a, R)

δ(q1, y) = (q1, y, R)

δ(q1, b) = (q2, y, L)

δ(q2, y) = (q2, y, L)

δ(q2, a) = (q2, a, L)

δ(q2, x) = (q0, x, R)

δ(q0, y) = (q3, y, R)

δ(q3, y) = (q3, y, R)

δ(q3, ◻) = (qf, ◻, R)

  1. L = {anbn|n ≥ 0}
  2. L= {anbn|n ≥ 1}
  3. L = {anbn|n > 0}
  4. L = {anbn|n > 1}

Answer (Detailed Solution Below)

Option 2 : L= {anbn|n ≥ 1}

Context Free Languages and Pushdown Automata Question 3 Detailed Solution

The correct answer is L = {anbn|n ≥ 1}.

key-point-imageKey Points

  • This Turing machine recognizes the language L = {anbn|n ≥ 1} which means it accepts strings where the number of 'a's is equal to the number of 'b's, and there is at least one 'a' and one 'b'.
  • The transition functions describe how the machine processes the input:
    • δ(q0,a) = (q1, x, R): When in state q0 and reading 'a', it replaces 'a' with 'x' and moves right, transitioning to state q1.
    • δ(q1,a) = (q1, a, R): When in state q1 and reading 'a', it keeps 'a' and moves right, staying in state q1.
    • δ(q1, y) = (q1, y, R): When in state q1 and reading 'y', it keeps 'y' and moves right, staying in state q1.
    • δ(q1, b) = (q2, y, L): When in state q1 and reading 'b', it replaces 'b' with 'y' and moves left, transitioning to state q2.
    • δ(q2, y) = (q2, y, L): When in state q2 and reading 'y', it keeps 'y' and moves left, staying in state q2.
    • δ(q2, a) = (q2, a, L): When in state q2 and reading 'a', it keeps 'a' and moves left, staying in state q2.
    • δ(q2, x) = (q0, x, R): When in state q2 and reading 'x', it keeps 'x' and moves right, transitioning to state q0.
    • δ(q0, y) = (q3, y, R): When in state q0 and reading 'y', it keeps 'y' and moves right, transitioning to state q3.
    • δ(q3, y) = (q3, y, R): When in state q3 and reading 'y', it keeps 'y' and moves right, staying in state q3.
    • δ(q3, ◻) = (qf, ◻, R): When in state q3 and reading blank (◻), it keeps the blank and moves right, transitioning to final state qf.

additional-information-imageAdditional Information

  • In state q0, the machine starts by marking an 'a' with 'x' and then searches for the corresponding 'b' to mark it with 'y'.
  • In state q1, the machine skips over 'a's and 'y's until it finds a 'b'.
  • In state q2, the machine moves left to revisit and check the marked 'x' and continues the process until all 'a's and 'b's are marked.
  • When all 'a's and 'b's are marked, the machine moves to state q3, where it verifies the marking and then transitions to the final state qf.

Context Free Languages and Pushdown Automata Question 4:

Choose the correct statement(s)

A. A problem which is NP-Complete will have the property that it can be solved in polynomial time iff all other NP-complete problems can also be solved in polynomial time.

B. All NP-complete problem are NP-hard problems.

C. If an NP-hard problem can be solved in polynomial time, then all NP-complete problem can be solved in polynomial time

D. All NP-hard-problems are not NP-complete.

Choose the correct answer from the options given below:

  1. A, C only
  2. B, D only
  3. A, B, C only
  4. A, B, C, D

Answer (Detailed Solution Below)

Option 4 : A, B, C, D

Context Free Languages and Pushdown Automata Question 4 Detailed Solution

- halleshangoutonline.com

The correct answer is Option 4.Key Points

  • Statement A: A problem which is NP-Complete will have the property that it can be solved in polynomial time iff all other NP-complete problems can also be solved in polynomial time.
    • This statement is correct. By definition, if one NP-complete problem can be solved in polynomial time, all NP-complete problems can be solved in polynomial time because they are all polynomial-time reducible to each other.
  • Statement B: All NP-complete problems are NP-hard problems.
    • This statement is correct. NP-complete problems are a subset of NP-hard problems, meaning every NP-complete problem is also NP-hard.
  • Statement C: If an NP-hard problem can be solved in polynomial time, then all NP-complete problems can be solved in polynomial time.
    • This statement is correct. If any NP-hard problem (which is not necessarily in NP) can be solved in polynomial time, it implies that P = NP, meaning all NP-complete problems can also be solved in polynomial time.
  • Statement D: All NP-hard problems are not NP-complete.
    • This statement is correct. NP-hard problems include both NP-complete problems and other problems that are not in NP.

Since statements A, B, C, and D are all correct, the correct answer is Option 4.

Context Free Languages and Pushdown Automata Question 5:

Consider the CFG with {S,A,B} as the non-terminal alphabet, {a,b} as the terminal alphabet, S as the start symbol and the following set of production rules :

S→bA            S → aB

A → a            B →b

A → aS          B→bS

S→ bAA         B → aBB

Which of the following strings is generated by the grammar? 

  1. aaaabb
  2. aabbbb
  3. aabbab
  4. Abbba

Answer (Detailed Solution Below)

Option 3 : aabbab

Context Free Languages and Pushdown Automata Question 5 Detailed Solution

The correct answer is aabbab

Explanation:

To determine which of the given strings can be generated by the grammar, let's analyze the grammar and systematically derive possible strings.

Grammar Rules:

  • Non-terminals: {S, A, B}
  • Terminals: {a, b}
  • Start Symbol: S
  • Production Rules:
    •   1. S → bA
    •   2. S → aB
    •   3. A → a
    •   4. A → aS
    •   5. S → bAA
    •   6. B → b
    •   7. B → bS
    •   8. B → aBB


Step 1: Understand the Structure of the Grammar

  • S generates strings starting with a or b :
    • S → bA : Starts with b and continues with A .
    • S → aB : Starts with a and continues with B .
  • A produces a , or appends aS .
  • B produces b , bS , or appends aBB .


The grammar supports recursive structures (e.g., S → bAA or B → aBB ) to generate strings of arbitrary length.

Step 2: Analyze Each Option
1. aaaabb :

  • Start with S → aB (produces a ).
  • B → aBB : Produces aBB , resulting in aaBB .
  • B → aBB : Produces aaaBBB .
  • B → aBB : Produces aaaaBBBB .
  • B → b : Produces aaaabBBB .
  • B → b : Produces aaaabbBB .
  • Invalid Cannot generate aaaabb structure


2. aabbbb :

  • Start with S → aB (produces a ).
  • B → aBB : Produces aaBB , resulting in aaBB .
  • B → b : Produces aabBb .
  • B → b : Cannot generate bbbb structure. Invalid.


3. aabbab :

  • Start with S → aB (produces a ).
  • B → aBB : Produces aBB , resulting in aaBB .
  • B → bS : Produces aabSB .
  • S → bA : Produces aabbAB .
  • A → a : Produces aaaabbaB .
  • B →  b: Produces aabbab .
  • Valid


4. Abbba :

  • Contains an uppercase A , which is a non-terminal. Invalid.


The string generated by the grammar is: 3) aabbab.

Top Context Free Languages and Pushdown Automata MCQ Objective Questions

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?

  1. I only
  2. II only
  3. I and III only
  4. III only

Answer (Detailed Solution Below)

Option 3 : I and III only

Context Free Languages and Pushdown Automata Question 6 Detailed Solution

Download Solution PDF

Concept:

Union of a Regular language and a Deterministic Context Free Language (DCFL) is a DCFL.

Explanation:

Statement I: TRUE.

L = {an |n ≥ 0} ∪ {anbn| n ≥ 0}

{an |n ≥ 0} is a regular language and {anbn| n ≥ 0} is a DCFL and hence, there Union would be a DCFL.

Statement II: FALSE.

L is DCFL then it is CFL too.

Statement III: TRUE

L cannot be LL(k) for any number of look-ahead. LL(k) cannot conclusively distinguish that whether the string to be parsed is from an or from anbn. Both have a common prefix.

Consider the following two Grammars:

G1 : S → SbS|a

G2 : S → aB|ab, A → AB|a, B → ABb|b

Which of the following option is correct?

  1. Only G1 is ambiguous
  2. Only G2 is ambiguous
  3. Both G1 and G2 are ambiguous
  4. Both G1 and G2 are not ambiguous

Answer (Detailed Solution Below)

Option 3 : Both G1 and G2 are ambiguous

Context Free Languages and Pushdown Automata Question 7 Detailed Solution

Download Solution PDF

Concept:

Ambiguous grammar:

A grammar in which there exists a string for which two derivation trees are possible, then it is known as ambiguous grammar.

Explanation:

G1: S → SbS|a

String: “ababa”

F1 R.S Madhu 13.04.20 D2

F1 R.S Madhu 13.04.20 D3

Two derivation trees (parse tree) is possible. So, grammar G1 is ambiguous

G2 : S → aB|ab, A → AB|a, B → ABb|b

String: “ab”

F1 R.S Madhu 13.04.20 D4

F1 R.S Madhu 13.04.20 D5

Two derivation trees (parse tree) is possible. So, grammar G2 is ambiguous

Consider L = L1 ∩ L2

Where L1 = {0m1m20n1n |m, n >= 0}

L2 = {0m1n2k | m, n, k ≥ 0}

Then, the language L is

  1. Recursively enumerable but not context free
  2. Regular
  3. Context free but not regular
  4. Not recursive

Answer (Detailed Solution Below)

Option 3 : Context free but not regular

Context Free Languages and Pushdown Automata Question 8 Detailed Solution

Download Solution PDF

The correct answer is option 3.

Key Points

  • L1 will first contain 0's followed by an equal number of 1's. After that, there will be a single 2 which will again be followed by 0's and an equal number of 1's i.e.   L1={2,012,00112,20011,01201,0011201,0120011,001120011,........}
  • L2={epsilon,0,1,2,01,12,012,00112,20011,01201,0011201,0120011,001120011,............}
  • L=L1∩L2={2,012,00112,0001112,........}
  • L=L1∩L2={0m1m2/ m>=0}, which is a context free language but not regular language.

∴ Hence the correct answer is Context-free but not regular.

Additional Information

F1 Shraddha Raju 03.04.2021 D30 

The language which is generated by the grammar S → aSa | bSb | a | b over the alphabet {a, b} is the set of

  1. Strings that begin and end with the same symbol
  2. All odd and even length palindromes
  3. All odd length palindromes
  4. All even length palindromes

Answer (Detailed Solution Below)

Option 3 : All odd length palindromes

Context Free Languages and Pushdown Automata Question 9 Detailed Solution

Download Solution PDF

Concept:

S → aSa | bSb | a | b generates strings like {a, b, aaa, bbb, aba, bab, abbba, ababa, ….) which is the set of all odd length palindromes.

Example of odd length pallindrom.

String:  ababa

F1 R.S 20.5.20 Pallavi D1

Option 1: Incorrect

String: “aa” (Not accepted)

Begins and ends with same symbol but not accepted by given grammar

Option 2 and 4: Incorrect

String: “aa” (Not accepted)

Even length palindrome is not accepted by given grammar

Suppose that L1 is a regular and L2 is a context-free language, Which one of the following languages is NOT necessarily context-free?

  1. L1 ⋅ L2
  2. L1 ∪ L2
  3. L1 ∩ L2
  4. L1 - L2

Answer (Detailed Solution Below)

Option 4 : L1 - L2

Context Free Languages and Pushdown Automata Question 10 Detailed Solution

Download Solution PDF

Concepts:

Operation under which context-free language is not closed: Intersection, complementation, set difference

Operation under which context-free language is closed: Union, Kleene Closure, and Concatenation.

Context-free language is closed under Intersection with regular language.

Explanation:

L1 is a regular and L2 is a context-free language.
Every regular language is context-free language.

Option 1: context-free language

\({L_1}.{L_2}\) it is the context-free language because it is closed under Concatenation.

Option 2:context-free language

L1 ∪ Lit is the context-free language because it is closed under Union.

Option 3: context-free language

\({L_1} \cap \;{L_2}\) it is the context-free language because context-free language is closed under Intersection with regular language.

Option 4: may not be context-free language

L1 - L2  it may not be context-free language because it is not closed under complementation.

Let G = (V, T, S, P) be any context-free grammar without any λ-productions or unit productions. Let K be the maximum number of symbols on the right of any production in P. The maximum number of production rules for any equivalent grammar in Chomsky normal form is given by:

Where |⋅| denotes the cardinality of the set.

  1. (K - 1)|P| + |T| -1
  2. (K - 1)|P| + |T|
  3. K |P| + |T| -1
  4. K |P| + |T|

Answer (Detailed Solution Below)

Option 2 : (K - 1)|P| + |T|

Context Free Languages and Pushdown Automata Question 11 Detailed Solution

Download Solution PDF

Concept:

Context free grammar : A grammar G = (V, T ,S, P) is said to be context- free if all productions in P have the form A -> x where A ϵ V and x ϵ (V U T)*.

Explanation:

If context free grammar G = (V, T, S, P) is without λ-productions or unit productions.

K = maximum number of symbols on right side of production.

The maximum number of production rules for equivalent grammar in CNF:

(K - 1)|P| + |T|

A context free grammar is in CNF (Chomsky normal form) if it satisfies these conditions:

1) Should not contains null or unit productions.

2) A non-terminal symbol generating two non-terminals. For example, S -> AB

3) A non- terminal generating a terminal. Example: S -> a

Consider the following languages:

\({L_1} = \left\{ {{a^n}{b^n}{c^m}} \right\} \cup \left\{ {{a^n}{b^m}{c^m}} \right\},\;n,\;m \ge 0\)

\({L_2} = \{ w{w^R}|w \in \left\{ {a,\;b} \right\}*\}\) Where R represents reversible operation.

Which one of the following is (are) inherently ambiguous language(s)?

  1. only L1
  2. only L2
  3. both L1 and L2
  4. neither L1 nor L2

Answer (Detailed Solution Below)

Option 1 : only L1

Context Free Languages and Pushdown Automata Question 12 Detailed Solution

Download Solution PDF

Concept:

Inherently ambiguous language: A context free language is inherently ambiguous if every context free grammar for that language is ambiguous.

Explanation:

If we get any one unambiguous grammar for each of the option given above, then that language will not be inherently ambiguous.

Case 1:

\({L_1} = \left\{ {{a^n}{b^n}{c^m}} \right\} \cup \left\{ {{a^n}{b^m}{c^m}} \right\},\;n,\;m \ge 0\)

This is inherently ambiguous language. There does not exist any unambiguous grammar for this. It is somewhat similar to the language L = {aibjck | i = j or j = k} . It has a common subset anbncn.

\({L_2} = \{ w{w^R}|w \in \left\{ {a,\;b} \right\}*\} \) Where R represents reversible operation.

This is not inherently ambiguous language. An unambiguous grammar exists for it:

S -> aSa | bSb |  λ

Context free languages are closed under

  1. union, intersection
  2. union, Kleene closure
  3. intersection, complement
  4. complement, Kleene closure

Answer (Detailed Solution Below)

Option 2 : union, Kleene closure

Context Free Languages and Pushdown Automata Question 13 Detailed Solution

Download Solution PDF

Concept:

Context free languages are closed under Union and Kleene Closure

CFL is not closed under intersection and not closed under complementation

Hence, only option 2 matches

Important Points:

Context free languages

Only Deterministic Context free languages

Closed under

  • Union
  • Concatenation
  • Kleene Closure
  • Homomorphism
  • Inverse Homomorphism
  • Reversal of language
  • Intersection with Regular language

Closed under

  • Complementation
  • Inverse Homomorphism

Not Closed under

  • Complementation
  • Intersection

Not Closed under

  • Union
  • Intersection
  • Concatenation
  • Kleene closure
  • Homomorphism
  • Reversal of language

Match List I with List II

List I

List II

Production Rules

Grammar

A.

S → XY

X → 0

Y → 1

I.

Greibach Normal Form

B.

S → aS| bSS |c

II.

Context Sensitive Grammar

C.

S → AB

A → 0A | 1A | 0

B → 0A

III. 

Chomsky Normal Form

D.

S → aAbc

Ab → bA

Ac → Bbcc

bB → Bb

aB → aa | aaA

IV.

S-Grammar


Choose the correct answer from the options given below :

  1. A ‐ III, B ‐ I , C ‐ IV, D ‐ II
  2. A ‐ III, B ‐ II , C ‐ I, D ‐ IV
  3. A ‐ III, B ‐ IV, C ‐ I, D ‐ II
  4. A ‐ IV, B ‐ III , C ‐ I, D ‐ II

Answer (Detailed Solution Below)

Option 3 : A ‐ III, B ‐ IV, C ‐ I, D ‐ II

Context Free Languages and Pushdown Automata Question 14 Detailed Solution

Download Solution PDF

The correct answer is option 3.

Solution :

List I

List II

Production Rules

Grammar

A.

S → XY

X → 0

Y → 1

III

Chomsky Normal Form

B.

S → aS| bSS |c

IV

S-Grammar

C.

S → AB

A → 0A | 1A | 0

B → 0A

Greibach Normal Form

D.

S → aAbc

Ab → bA

Ac → Bbcc

bB → Bb

aB → aa | aaA

II

Context Sensitive Grammar

 

Important Points 

A context free grammar (CFG) is in Greibach Normal Form (GNF) if all production rules satisfy one of the following conditions:

  • A non-terminal generating a terminal (e.g.; X->x)
  • A non-terminal generating a terminal followed by any number of non-terminals (e.g.; X->xX1X2…XN)

 

A context free grammar (CFG) is in Chomsky Normal Form (CNF) if all production rules satisfy one of the following conditions:

  • A non-terminal generating a terminal (e.g.; X->x)
  • A non-terminal generating two non-terminals (e.g.; X->YZ)
  • Start symbol generating ε. (e.g.; S-> ε)

Note : Left side of the given table contains the standard form of the grammar.

Which of the following grammars is (are) ambiguous?

(A) s → ss | asb | bsa | λ

(B) s → asbs | bsas | λ

(C) s → aAB

A → bBb

B →  A | λ where λ denotes empty string

Choose the correct answer from the options given below:

  1. (A) and (C) only
  2. (B)only 
  3. (B) and (C) only
  4. (A) (B) and (C)

Answer (Detailed Solution Below)

Option 4 : (A) (B) and (C)

Context Free Languages and Pushdown Automata Question 15 Detailed Solution

Download Solution PDF

The correct answer is option 4.

Key Points

A is ambiguous because λ can be generated using leftmost derivation having two different parse trees with an empty string.

F1 Shraddha Raju 03.04.2021 D26

B is ambiguous grammar with string abab.

F1 Shraddha Raju 03.04.2021 D27

C is an ambiguous grammar with string abbbb.

F1 Shraddha Raju 03.04.2021 D28

∴ Hence the correct answer is (A) (B) and (C).

Get Free Access Now
Hot Links: teen patti gold online teen patti cash game teen patti chart teen patti - 3patti cards game all teen patti game