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 :
Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 1 Detailed Solution
The correct answer is Not Recursive.
Key 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
- 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 :
Answer (Detailed Solution Below)
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-terminalS
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)
Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 3 Detailed Solution
The correct answer is L = {anbn|n ≥ 1}.
Key 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
- 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:
Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 4 Detailed Solution
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?Answer (Detailed Solution Below)
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?Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 6 Detailed Solution
Download Solution PDFConcept:
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?Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 7 Detailed Solution
Download Solution PDFConcept:
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”
Two derivation trees (parse tree) is possible. So, grammar G1 is ambiguous
G2 : S → aB|ab, A → AB|a, B → ABb|b
String: “ab”
Consider L = L1 ∩ L2
Where L1 = {0m1m20n1n |m, n >= 0}
L2 = {0m1n2k | m, n, k ≥ 0}
Then, the language L is
Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 8 Detailed Solution
Download Solution PDFThe 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
The language which is generated by the grammar S → aSa | bSb | a | b over the alphabet {a, b} is the set of
Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 9 Detailed Solution
Download Solution PDFConcept:
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
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 grammarSuppose that L1 is a regular and L2 is a context-free language, Which one of the following languages is NOT necessarily context-free?
Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 10 Detailed Solution
Download Solution PDFConcepts:
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 ∪ L2 it 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.
Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 11 Detailed Solution
Download Solution PDFConcept:
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)?Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 12 Detailed Solution
Download Solution PDFConcept:
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
Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 13 Detailed Solution
Download Solution PDFConcept:
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
|
Closed under
|
Not Closed under
|
Not Closed under
|
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 :
Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 14 Detailed Solution
Download Solution PDFThe 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 |
I |
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:
Answer (Detailed Solution Below)
Context Free Languages and Pushdown Automata Question 15 Detailed Solution
Download Solution PDFThe 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.
B is ambiguous grammar with string abab.
C is an ambiguous grammar with string abbbb.
∴ Hence the correct answer is (A) (B) and (C).