Time Left - 15:00 mins

# GATE CS 2021 : Theory of computation Quiz 4

Attempt now to get your rank among 622 students!

Question 1

Any string of terminals that can be generated by the following CFG satisfy which of the given choices?

S → XY

X → aX | bX | a

Y → Ya | Yb | a

Question 2

Consider the following PDA state transition function

δ (q1,a,z0) = (q1,az0)

δ (q1,a,a) = (q1,aa)

δ (q1,b,a) = (q2,€)

δ (q2,b,a) = (q2,€)

δ (q2,c,a) = (q3,€)

δ (q3,c,a) = (q3,€)

δ (q3,€,z0) = (qf,z0)

where initial states ={q1}, states={q1,q2,q3,qf}, final state={qf} and stack alphabet={a,b,c,z0}.find the

language satisfy by the above given state transition function.

Question 3

Consider the following language a

^{n}b^{2n+1}. The minimum number of states needs to draw PDA with acceptance by final state?Question 4

Match the following items from the table

Question 5

Context free grammar refers to the following type of automata strictly

Question 6

Which of the following CFGs generates a CFL but not regular?

- 622 attempts
- 4 upvotes
- 3 comments

Oct 3GATE & PSU CS

Posted by: