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

The correct answer is Not Recursive.

Key Points

• Let L = L1 ∩ L2 where L1 and L2 are languages defined below :
  • L1 = {a^mb^mc^anbⁿ | m, n ≥ 0}
  • L2 = {aⁱb^jc^k | 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.

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.

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.

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.

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.

Concept:

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

Explanation:

Statement I: TRUE.

L = {aⁿ |n ≥ 0} ∪ {aⁿbⁿ| n ≥ 0}

{aⁿ |n ≥ 0} is a regular language and {aⁿbⁿ| 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 aⁿ or from aⁿbⁿ. Both have a common prefix.

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:

G₁: S → SbS|a

String: “ababa”

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

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

String: “ab”

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={0^m1^m2/ m>=0}, which is a context free language but not regular language.

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

Additional Information

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

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)

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 ∪ 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.

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

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 = {aⁱb^jc^k | i = j or j = k} . It has a common subset aⁿbⁿcⁿ.

\({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 |  λ

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:

The correct answer is option 3.

Solution :

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.

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.

B is ambiguous grammar with string abab.

C is an ambiguous grammar with string abbbb.

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