Time Left - 15:00 mins

# GATE CS 2021 : Theory of computation Quiz 4

Attempt now to get your rank among 637 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 satisfied 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?
• 637 attempts GradeStack Learning Pvt. Ltd.Windsor IT Park, Tower - A, 2nd Floor, Sector 125, Noida, Uttar Pradesh 201303 bepstudentsupport@byjus.com