in Theory of Computation
356 views
1 vote
1 vote
HI,

I would like someone to give clarification on how to identify a string is which grammar. I am not able to understand the concept well. So if someone explains ii, it will be highly appreciated. Please give examples.

for eg: { a^n } is CFG or not.

Thank you.
in Theory of Computation
by
356 views

1 Answer

4 votes
4 votes
1. If you can express the language as a regular expression then the language is Regular

eg: $a^{n},n \geq 0$ is a regular language.

2. If you can recognize the language with a stack machine (Push Down automata), then it is a context free language.

eg $a^{n}b^{n},n \geq 0$ is a context free language.

3. If you can recognize the language with a Linear bound automaton (Turing machine with a finite tape), then its a context sensitive language.

4. If you cannot construct any of the above , then it belong to Phase structured language.

Turing machine can be constructed for recognizing any recursively enumerable language.
edited by

4 Comments

Still there are languages outside Turing recognizable. Turing recognizable means recursively enumerable languages.
1
1
Yes thats true. I'll edit the answer.
1
1
thank you sir.
0
0