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