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={anbn | n>=1}{anb2n | 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 = anbn :

We want to check whether the string a4b4 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.

[Example: In above table
Initially stack is empty.
Consider the following languages.

How many of the above language are subset of the language L where L is the language accepted by the given PDA?(Assume PDA acceptance is by empty stack method)

Question 6

What is the size of stack required to accept a string of pattern anbn if n = 13?
• 184 attempts
• 1 upvote

Tags :

Oct 10GATE & PSU CS
GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 help@byjusexamprep.com