The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.5k views

Which of the following is true for the language

$$\left\{ a^p \mid p \text{ is a prime } \right \}?$$

  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
asked in Theory of Computation by Veteran (59.7k points) | 1.5k views

2 Answers

+21 votes
Best answer

We have algorithms to generate prime numbers $\implies$ we can generate sequence of $p$ for the given language, hence strings as defined by the language definition.

So, by Church Turing Thesis we can say that there exists a Turing Machine which can accept the given language.

Answer is option D.

answered by Boss (30.9k points)
edited by
+3
It is CSL so it will be accepted by LBA hence it can also be accepted by Turing Machine. Is this approach is correct ?
0
so what is type of language ?

is it recursive .
0
@akash.dinkar

there is one statement in link you provided

"NDTM halts on every input and language accepted by NDTM will be CSL "

Do you know any reference for this?

I tried to search on net , i did not find anything useful
0 votes
Ans is (D)
answered by Loyal (6.2k points)
0
please explain how come TM accepts it?
+2
Because It is a CSL and it can be easily accepted by Linear Bound Aoutomata, hence accepted by Turing Machine. therfore D)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,474 questions
49,930 answers
165,530 comments
65,900 users