Time Left - 15:00 mins

GATE 2022: Theory Of Computation Quiz-4

Attempt now to get your rank among 184 students!

Question 1

How many of the following CFGs generates a CFL but not regular?
(i)

(ii)

(iii)

Question 2

Consider the following context free language (CFL)

L={aⁿbⁿ |n>=1}∪{aⁿb²ⁿ| n>=1}

A minimum number of states that are present in the state transition diagram of the above CFL

Question 3

Consider a PDA which has 4 states. We have 3 alphabets (a,b,c) in a string. On first state , there are 3 transitions possible. Transition 1 : if "a" comes and stack is empty , then push it and remain on same state. Transition 2 : if "a" comes and stack is not empty , top symbol is also "a" , then also push "a" and remain on same state. Transition 3 : if "c" comes and top of stack is "a" then skip "c" and move to second state. Now in second state , it has 2 transitions. Transition 1 : if "c" comes and top of stack is "a" then skip "c" and remain on same state. Transition 2 : If "b" comes and top of stack is "a" , pop it and move to third state. Third state has 3 transitions. Transition 1 : If "b" comes and top of stack is "a" , pop it and remain on same state. Transition 2 : If "$" comes and stack is empty then go to the final state 4.

The above PDA is accepting which of the following language :

Question 4

Consider the following PDA for L = aⁿbⁿ :

We want to check whether the string a⁴b⁴ belongs to the language L or not. A single move in PDA causes 5 nanoseconds delay. Find the total delay in nanoseconds to check the membership of the string.

Question 5

Consider the following transition table from PDA.