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 anb2n+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:

Harshita AgarwalHarshita AgarwalMember since Jul 2020
Share this quiz   |