Computer science: Theory Of computation MCQs

The languageL = {0i 21i | i>=0} over the alphabet {0,1,2} is:

 not recursive
 is recursive and is a deterministic CFL.
 is a regular language.
 is not a deterministic CFL but a CFL.

Answer

 {wwR | w ϵ {0,1}+}
 {wwRx | x,w ϵ {0,1}+}
 {wxwR | x,w ϵ {0,1}+}
 {xwwR | x,w ϵ {0,1}+}

Answer

 b*ab*ab*ab*
 (a+b)*
 b*a(a+b)*
 b*ab*ab*

Answer

 1
 2
 3
 4

Answer

 It is not accepted by a Turing Machine
 It is regular but not context-free
 It is context-free but not regular
 It is neither regular nor context-free, but accepted by a Turing machine

Answer