302 views

1 Answer

Best answer
1 votes
1 votes

Hi, 
There are multiple ways to do this, let's go with one class at a time: 
1: Testing for Regular Language: If you are given with a grammar, just check if it is right or left linear if it is then it's language is regular. Next you can try to give a FA, or a Regular expression, if you can do so, then it is regular. One thing to note is that any regular language will never have infinite matching or counting between two symbols. 
Another way is to see of the strings of the language are in AP or not. Eg: L={a,aa,aaa,aaaa,aaaaa.............} 
2: Testing for CFL: Here you can try to give a PDA. Here you don't need to draw the PDA with each and every transition but what you can do is you can mentally think if the kind of comparision that is given in the language between two symbols can be done with the help of stack or not. One thing to note is that you cannot compare three symbols (a^nb^nc^n) infinitely in CFLs, however you can very easily compare two symbols (a^nb^n). 

3: There is no point is differentiating between CSL and RecursiveLs. 
4: Recursive Language and RELs: You can see how does the language and its complement behave, because Recursive languages are closed under complementation, so you can easily differentiate. One other way is to see if the TM halts on every input or not. Even if for one input if the language runs infinitely then it is not Recursive. 
PS: If you found the answer to be helpful please consider upvoting!

selected by

Related questions