## 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 { a ^{n}b^{n }| 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 = { 0 ^{i }1^{j} | i != j }**

**L2 = { 0 ^{i }1^{j }| i = j }**

**L3 = { 0 ^{i }1^{j }| i = 2j+1}**

**L4 = { 0 ^{i }1^{j} | 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 = { a ^{m} b^{m} c a^{n} b^{n} | m, n >= 0 }**

**L2 = { a ^{i }b^{j }c^{k} | 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 = { a^{k} b^{k} 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?**

- {a
^{m}b^{n}| n >= m, m > 0} - {a
^{m}b^{n}| n >= m, m > =0} - {a
^{m}b^{n}| n > m, m > 0} - {a
^{m}b^{n}| 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 = { a ^{n} b^{n} c^{m} | n, m > 0 }**

**L2 = { a ^{n} b^{m} c^{m} | 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 = { a ^{m} b^{n} a^{n} b^{m} | m, n > 0 }**

**L2 = { a ^{m} b^{n}, a^{m}, b^{n} | m, n > 0 }**

**L3 = { a ^{m} b^{n }| 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__