Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Context-free languages and pushdown automata questions
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Context-free languages and pushdown automata Questions

Author Teesha Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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?

  1. Single-Tape and Multi-Tape Turing machine
  2. Deterministic and Non-deterministic pushdown automata
  3. Deterministic and Non-deterministic finite automata
  4. 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:

  1. All even length palindromes.
  2. All palindromes.
  3. All odd length palindromes.
  4. 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 { anb| n ϵ N }. Then which of the following is always regular?

  1. P ∩ Q
  2. P - Q
  3. Σ* - P
  4. Σ* - 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 = { 01j | i != j }

L2 = { 01| i = j }

L3 = { 01| i = 2j+1}

L4 = { 01j | i != 2j }

Which option is correct

  1. All the context-free
  2. Only L2 is context-free
  3. Only L1 and L3 are context-free
  4. 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 = { abck | i, j, k >= 0 }

Now if L = L1 ∩ L2. Then L is 

  1. Not recursive
  2. Regular
  3. context-free but not regular 
  4. 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:

  1. aaaabb
  2. aabbbb 
  3. aabbab
  4. 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. 1
  2. 2
  3. 3
  4. 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

  1. Context-free, linear
  2. Context-free, non-linear
  3. Non-context-free, linear
  4. 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?

  1. {am bn | n >= m, m > 0}
  2. {am bn | n >= m, m > =0}
  3. {am bn | n > m, m > 0}
  4. {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?

  1. aabbaba
  2. aabaaba
  3. abababb
  4. 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?

  1. l <=  P >= r
  2. l = P = r
  3. l >= P >= r
  4. 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-

  1. Union, Intersection
  2. Union, Kleen Closure
  3. Intersection, Complement
  4. 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

  1. Only c
  2. Only b
  3. Both a and c
  4. 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. { ϵ }
  2. { ϵ, 1 } 
  3. φ 
  4. 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 → ϵ

  1. 10
  2. 15
  3. 12
  4. 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?

  1. L1 ∩ L2 is a context-free language.
  2. L1 U L2 is a context-free language
  3. L1 and L2 are context-free languages
  4. 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?

  1. A deterministic push-down automaton always accepts a context-free language.
  2. Union is closed under context-free language.
  3. The language formed by the intersection of two context-free languages is also context-free.
  4. 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 b| m = 2n +1 }

Which of the these languages are context-free?

  1. L1 and L2 only
  2. L1 and L3 only
  3. L2 and L3 only
  4. 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

  1. Context-free
  2. Regular
  3. Deterministic context-free
  4. 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?

  1. Union
  2. Complementation
  3. Kleen star
  4. 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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

  1. What is the theory of computation?
    Theory of computation is a theoretical branch of computer science and mathematics that deals with the study of abstract machines and the computational problem that can be solved using these machines.
     
  2. What do DFA and NFA stand for?
    DFA stands for deterministic finite automata, and NFA stands for non-deterministic finite automata.
     
  3. What do you mean by NFA?
    Non-deterministic finite automata (NFA) is a type of finite automata when there exist many paths with a single input from one state to the next state.
     
  4. What is Moore's and Mealy’s machine?
    Moore’s machine is an FSM where output depends on only the present state. Mealy’s machine is an FSM whose output depends on the present state as well as the present input

Key Takeaways

In this article, we discussed the previous year's gate questions on Context-free languages and pushdown Automata. We have discussed the answers to the questions with an explanation. Hope you would have gained a better understanding of these topics now!

Check out this problem - Check If A String Is Palindrome

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!
 

Happy Coding!

Previous article
Regular languages and finite automata
Next article
Recursively enumerable sets and Turing machines Questions
Live masterclass