in Theory of Computation
5,210 views
20 votes

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
in Theory of Computation
5.2k views

1 comment

TM is supposed to be the equivalent of modern computer.

Now in modern computer we can write program to find prime numbers.i.e there is an algorithm to do this.

so,this is accepted by TM, moreover it's a Recursive language(halting TM).
3

Subscribe to GO Classes for GATE CSE 2022

3 Answers

30 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.

edited by

5 Comments

It is CSL so it will be accepted by LBA hence it can also be accepted by Turing Machine. Is this approach is correct ?
6
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
yes
0
1 vote

There ar some languages which except by LBA.( Must for Gate Aspirants)

See the 4th point which says the given language is CSL.

so it is neither Regular nor CFL, but it is CFL so it is must it is accepted by Turing machine. 

 

0 votes
Ans is (D)

4 Comments

please explain how come TM accepts it?
0
Because It is a CSL and it can be easily accepted by Linear Bound Aoutomata, hence accepted by Turing Machine. therfore D)
4
why is it not Regular…. as in we can form NFA for it ??
0
The language given in the question is a well known example of CSL, and it can be proved that it is not RL or CFL using their respective pumping lemmas.
0
Answer:

Related questions