开发者

How do you classify languages into regular, context free, and phrase-structure?

开发者 https://www.devze.com 2022-12-30 01:05 出处:网络
If you\'re given a language, how do you figure out if it\'开发者_如何学Cs regular, CF but not regular, or phrase-structure but not CF? Is there a good way to attack this problem? I could randomly try

If you're given a language, how do you figure out if it'开发者_如何学Cs regular, CF but not regular, or phrase-structure but not CF? Is there a good way to attack this problem? I could randomly try to make FAs or PDAs, but I feel like there's a better way to do it.

Classic example:

L = { a^n b^n c^n | n >= 0 }

Where would one start? Thanks.


You sort of get a feel for classifying them. I don't know of a very methodical approach. Since languages are usually subsets and supersets of each other, you estimate where it fits in that hierarchy and show that it can't be, say, a regular language, but it could be a CFL.

0

精彩评论

暂无评论...
验证码 换一张
取 消