recategorized by
1,025 views
1 votes
1 votes

Let $L=\{a^p\mid p \text{ is a  prime}\}.$ Then which of the following is true

  1. It is not accepted by a Turing Machine
  2. It is regular but not context-free
  3. It is context-free but not regular
  4. It is neither regular nor context-free ,but accepted by a Turing Machine
recategorized by

1 Answer

Best answer
3 votes
3 votes

The language is an example of Context Sensitive Language which is not context free, therefore, it will be accepted by a Turing Machine. Option D is the correct answer.

selected by
Answer:

Related questions

5 votes
5 votes
2 answers
1
gatecse asked Dec 17, 2017
1,192 views
Which of the following are context-free?$A=\{a^n b^n\, a^mb^m\mid m,n\geq0\}$$B=\{a^m b^n\, a^mb^n\mid m,n\geq0\}$$C=\{a^mb^n\mid m\neq 2n,\,m,n\geq0\}$A and B only A and...
4 votes
4 votes
1 answer
2
3 votes
3 votes
2 answers
3
gatecse asked Dec 17, 2017
1,990 views
Identify the language generated by the following grammar$S\rightarrow AB\\ A\rightarrow aAb\mid \varepsilon\\ B\rightarrow bB\mid b$$\{a^m b^n\mid n\geq m,m>0\}$ $\{a^m b...
4 votes
4 votes
2 answers
4
gatecse asked Dec 17, 2017
3,376 views
Consider the grammar with productions$S\rightarrow aSb\mid SS \mid \varepsilon$This grammar is not context-free, not linearnot context-free, linearcontext-free, not linea...