Introduction
This article will discuss the questions that appeared previously in the gate exam in the theory of computation section. Here we will discuss the questions on context-free languages and pushdown Automata. Let's get started and discuss some questions.
Context-free languages and pushdown automata questions
1. Of the given pairs, which pair has a DIFFERENT expressive power?
- Single-Tape and Multi-Tape Turing machine
- Deterministic and Non-deterministic pushdown automata
- Deterministic and Non-deterministic finite automata
- Deterministic and Non-deterministic Single-tape Turing machine
Answer: B
Explanation: All the single tape turning machines can be converted into multi-tape turning machines, so they have the same expressive power; therefore, option A is incorrect. Also, every DFA can be converted to NFA, and every NFA can be converted to DFA; therefore, option C is incorrect. Similarly, option D is incorrect. But not all Non-deterministic pushdown automata can be converted to deterministic pushdown automata. So they have different expressive power. Hence the answer is option B.
2. Consider a grammar S -> aSa|bSb|a|b; And alphabet {a,b}. The language generated by the given grammar over the given alphabet is a set of:
- All even length palindromes.
- All palindromes.
- All odd length palindromes.
- Strings that begin and end with the same symbol.
Answer: C
Explanation: Here, the production aSa and bSb ensures that the generated string would be a palindrome, and we can generate aba, aaaaa, bab, etc., which is the odd length of palindromes only by the given grammar. Therefore, the correct option is C.
3. Let Q be a context-free language, and P be a regular language such that Q is a subset of P. For example, let P be a language given by the regular expression a*b* and Q be a context-free language given by { anbn | n ϵ N }. Then which of the following is always regular?
- P ∩ Q
- P - Q
- Σ* - P
- Σ* - Q
Answer: C
Explanation: Here, the first option is incorrect because P ∩ Q will be Q as Q is a subset of P, which is not regular. P - Q is equal to P - (P ∩ Q), which is also not regular. Σ* - Q is the complement of Q, which is neither context-free nor regular. Now, Σ* - P is the complement of P, so it is regular. Therefore correct option is C.
4. Consider the languages
L1 = { 0i 1j | i != j }
L2 = { 0i 1j | i = j }
L3 = { 0i 1j | i = 2j+1}
L4 = { 0i 1j | i != 2j }
Which option is correct
- All the context-free
- Only L2 is context-free
- Only L1 and L3 are context-free
- Only L4 is context-free
Answer: A
Explanation: In L1, L2 and L4, we need only one comparison to check the condition; hence they are context-free languages. Now, L3 follows some pattern that is i is equal to 2j+1, so it is regular. All regular languages are context-free; hence it is also context-free. Therefore Option A is correct.
5. Consider two languages L1 and L2 defines as
L1 = { am bm c an bn | m, n >= 0 }
L2 = { ai bj ck | i, j, k >= 0 }
Now if L = L1 ∩ L2. Then L is
- Not recursive
- Regular
- context-free but not regular
- Recursively enumerable but not context-free language.
Answer: C
Explanation: Here L = L1 ∩ L2 = { ak bk c | k >=0 }. We can see that this is not regular but it is context-free language.
6. Consider a context-free language with {S, A, B} as the variable alphabet, {a,b} as the terminal alphabet with S as the start symbol and following production rules:
S → aB S → bA
B → b A → a
B → bS A → aS
B →aBB A → bAA
The grammar above generates which of the following strings:
- aaaabb
- aabbbb
- aabbab
- abbbba
Answer: C
Explanation: By applying the production rules in the following sequence, we can generate aabbab.
Starting with S → aB (using S → aB)
→ aaBB (using B → aBB)
→ aabB (using B → b)
→ aabbS (using B → bS)
→ aabbaB (using S → aB)
→ aabbab (using B → b)
7. For the correct answer string of the above question, how many derivations trees can be made?
- 1
- 2
- 3
- 4
Answer: B
Explanation: Following are the only two derivation trees for string aabbab when considering the left-most derivations.
8. Consider the grammar with productions
S → aSb | SS | ϵ
This grammar is
- Context-free, linear
- Context-free, non-linear
- Non-context-free, linear
- Non-context-free, non-linear
Answer: B
Explanation: By Chomsky Hierarchy, grammar is context-free if all the production rule A → B have A as a single non-terminal and B as a set of terminal and non-terminal. Since all the production rules hold good, therefore, it is context-free. To be linear, a context-free grammar should have at most one non-terminal at the right side of the production rule, but here we have S → SS which has two non-terminals at the right side; therefore, it is non-linear. Hence option B is correct.
9. Consider the grammar
S → AB
A → aAb | ϵ
B → bB | b
What is the language generated by the given grammar?
- {am bn | n >= m, m > 0}
- {am bn | n >= m, m > =0}
- {am bn | n > m, m > 0}
- {am bn | n > m, m >= 0}
Answer: D
Explanation: Here starting symbol is S, so first comes A, then B (using S → AB). Now using A → aAb will generate an equal number of a and b. B → bB | b produce some more b. So the number of b is always greater than the number of a. Also, we have A → ϵ. Therefore, the number of a can also be zero. Hence, the correct option is D.
10. Consider the following grammar
S → aS | A
A→ aAb | bAa | ϵ
Given S is the starting symbol, A is a non-terminal, and a,b is terminal. Which of the following string is generated by the above grammar?
- aabbaba
- aabaaba
- abababb
- aabbaab
Answer: D
Explanation: By following the below sequence, we can generate the string aabbaab
Starting with S → aS (using S → aS)
→ aA (using S → A)
→ aaAb (using A → aAb)
→ aabAab (using A → bAa)
→ aabbAaab (using A → bAa)
→ aabbaab (using A → ϵ)
11. Let G be a context-free grammar. Let P be the number of parse trees, l be the number of left-most derivations, r be the number of rightmost derivations. We have a string w and have calculated the values of P, l and r. What should be the relation between P, l and r?
- l <= P >= r
- l = P = r
- l >= P >= r
- None of these
Answer: B
Explanation: For any context-free grammar, the number of left-most derivations, the number of rightmost derivations and the number of parse trees are equal.
12. Which among the following does the CFGs close under-
- Union, Intersection
- Union, Kleen Closure
- Intersection, Complement
- Complement, Kleen Closure
Answer: B
Explanation: CFGs are closed under Union, Concatenation and Kleene closure but not in Intersection and Complement. Therefore, Option B is correct.
13. Let L1 be a context-free language and L2 be a regular language. Which of the following is/are False?
a. L1 - L2 is not context-free
b. L1 ∩ L2 is context-free
c. ~L1 is context-free
d. ~L2 is regular
- Only c
- Only b
- Both a and c
- Both b and c
Answer: C
Explanation: Since L1 is context-free and L2 is regular, L1 - L2 is context-free. Also, the complement of L1 is not context-free as CFLs are not closed under complement. Therefore a and c are false. Hence option C is correct.
14. Consider the two languages L1 = φ and L2 = { 1 }. Then L1* ∪ L1 * L2* is represented by which of the following?
- { ϵ }
- { ϵ, 1 }
- φ
- 1*
Answer: D
Explanation: L1* is also φ and L2* is 1*. L1*L2* is 1*. Now L1* ∪ 1* is also 1*.
15. To derive the string ((() ()) ()), How many steps would be required if the grammar has the below production rules:
S → SS
S → (S)
S → ϵ
- 10
- 15
- 12
- 16
Answer: 10
Explanation: The following steps would be required to generate ((() ()) ())
S → (S) [S → (S) ]
→ (SS) [S → SS ]
→ ((S)S) [S → (S) ]
→ ((SS)S) [S → SS ]
→ (((S)S)S) [S → (S) ]
→ ((() S)S) [S → ϵ ]
→ ((() (S))S) [S → (S) ]
→ ((() ()) S) [S → ϵ ]
→ ((() ()) (S)) [S → (S) ]
→ ((() ()) ()) [S → ϵ ]
16. Consider the two languages L1 and L2
L1 = { an bn cm | n, m > 0 }
L2 = { an bm cm | n, m > 0 }
Which of the following statements is False?
- L1 ∩ L2 is a context-free language.
- L1 U L2 is a context-free language
- L1 and L2 are context-free languages
- L1 ∩ L2 is a context-sensitive language
Answer: A
Explanation: L1 intersection L2 will only have the common parts of L1 and L2, which is not context-free. Hence, option A is correct.
17. Which of the following statements is true?
- A deterministic push-down automaton always accepts a context-free language.
- Union is closed under context-free language.
- The language formed by the intersection of two context-free languages is also context-free.
- Context-free language is closed under complement.
Answer: B
Explanation: The union of two context-free languages is also context-free; therefore, union is closed under context-free languages.
18. Consider three languages
L1 = { am bn an bm | m, n > 0 }
L2 = { am bn, am, bn | m, n > 0 }
L3 = { am bn | m = 2n +1 }
Which of the these languages are context-free?
- L1 and L2 only
- L1 and L3 only
- L2 and L3 only
- L3 only
Answer: B
Explanation: context-free language is accepted by pushdown automata, and pushdown automata use a stack. So L1 and L2 can be accepted by the pushdown automata; hence they are context-free.
19. A language that is accepted by pushdown automata in which there is a restriction of 10 items on the stack best describes which language
- Context-free
- Regular
- Deterministic context-free
- recursive
Answer: B
Explanation: A pushdown automation accepts context-free languages. Context-free languages have no restriction on the length of the string. Still, in this question, it is given that the length is limited to 10, so such a language should also be accepted by the finite automata, and finite automata only accept regular language, so the answer is option B.
20. Context-free grammar is not closed under which of the following?
- Union
- Complementation
- Kleen star
- Product
Answer: B
Explanation: CFG is closed under union, product(concatenation) and Kleen closure, but it is not closed under intersection and complementation.
Check out this article - Converting NFA to DFA