356 views
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.

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.

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

1 vote
1
258 views