CS402 ( Theory of Automata ) Paper Fall 2011

1) Which non-CFL is accepted by the above given TM

2) Given CFG

S ---> 0AS|0

A ---> S1A|SS|1a

Generate string 0000100 from the given productions also show each step of derivation

3) Consider the language L which is EVEN-EVEN, defined over sigma = {a, b} Determine In how many distinct classes L partitions the sigma*. Explain briefly

4)

a) Write the Regular Expression for the language which generates the strings of length 6 starting and ending in same double letters defined over sigma = { a, b}

b) Write the Regular Expression for the language which accepts the strings containing 111 or 11 and no more 1's defined over sigma = { 0, 1 }

Questions of 3 and 2 marks

1) Differentiate wanted and unwanted strings

2) What are distinguishable and indistinguishable strings?

3) Write the pref(Q in R ) for the given languages (2 languages for Q are R were given

Which i forgot)

4) How an FA can be obtained for the given language and how the language can be determined for the given FA

5) What are the halt states of a PDA?

6) Describe whether Automata Theory is theoretical subject of programming subject