Classify the following languages as either A. regular, B. context free but not r
ID: 3696073 • Letter: C
Question
Classify the following languages as either
A. regular,
B. context free but not regular,
C. recursive but not context free, or
D. not recursive,
and explain for each why you chose that answer. You do not have to give detailed
proofs—just give one or two sentences that outline how you would prove your
classifi cation.
a. {m#x | m encodes a TM and x is a string it accepts}
b. {anbncn}
c. {x {a, b}* | the number of as in x is the same as the number of bs in x}
d. {anb2n}
e. {p | p is a recognition method that is syntactically legal (that is, it can be parsed
using a standard grammar for Java)}
f. the set of strings that contain the Java statement while(true){}
g. {(p, x) | p is a recognition method that, when run on the input x, executes the
statement while(true){}}
h. {p | p is a recognition method and L(p) {}}
i. {m | m encodes a TM M with L(M) {}}
j. {xx | x {a, b, c }* }
k. {(m, x) | m encodes a TM M that, when run on the input x, visits a state q7}
l. L(a*b*) L((a + ba*b)*)
m. {xxR | x {0, 1}*}
Explanation / Answer
Answer:
A. It is recursive enumerable since no TM can solve it.
B anbncn is recursive since its not possible to design pda for it.
C is context free since we can design a pda for it.
D. is context free we can design a dpda for it
E. its not recursive since no turing machine recognises it
F. it is context free since while true can be converted to a CFG.
G. It is not recursive since this problem can be reduced to halting problem.
H. It is recrsive since it can be simulated on a multi tape turing machine.
I. it is recursive enumerabke or undecidable.
J . It is recrsive we can design a TM for it
K it is not recursive enumerable since it is partially decidable only.
L. It is regular since intersection of two regular is regular.
M. It is context free since we can design npda for it.