656 views
1 votes
1 votes
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 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.

Related questions

1 votes
1 votes
1 answer
1
shikharV asked Nov 29, 2015
414 views
Given answer: APlease explain
0 votes
0 votes
3 answers
2
8 votes
8 votes
3 answers
3
Parshu gate asked Nov 13, 2017
15,199 views
Suppose we are given a grammar and asked to find the type of that grammar , what is the algorithm which needs to be followed for each of them? LL(1), OR LR(0) , OR CLR(1...
0 votes
0 votes
1 answer
4
shikharV asked Nov 19, 2015
462 views