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

Posted by confused on Stack Overflow See other posts from Stack Overflow or by confused
Published on 2010-05-11T01:03:58Z Indexed on 2010/05/11 1:14 UTC
Read the original article Hit count: 351

Filed under:

language-theory

|

regular-language

|

context-free-grammar

If you're given a language, how do you figure out if it's 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.

© Stack Overflow or respective owner

Related posts about language-theory

What is the exact problem with multiple inheritance?

as seen on Stack Overflow - Search for 'Stack Overflow'
I can see people asking all the time whether multiple inheritance should be included into the next version of C# or Java and C++ folks, who are fortunate enough to have this ability, say that this is like giving someone a rope to eventually hang themselves. What’s the matter with the multiple inheritance… >>> More
Theory of formal languages - Automaton

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi everybody ! I'm wondering about formal languages. I have a kind of parser : It reads à xml-like serialized tree structure and turn it into a multidimmensionnal array. I figured out that i need at least three variables to achieve the job : $tree = array(); // a new array $pTree = array(&$tree);… >>> More
How do you classify languages into regular, context free, and phrase-structure?

as seen on Stack Overflow - Search for 'Stack Overflow'
If you're given a language, how do you figure out if it's 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… >>> More
What exactly are administrative redexes after CPS conversion?

as seen on Stack Overflow - Search for 'Stack Overflow'
In the context of Scheme and CPS conversion, I'm having a little trouble deciding what administrative redexes (lambdas) exactly are: all the lambda expressions that are introduced by the CPS conversion only the lambda expressions that are introduced by the CPS conversion but you wouldn't have written… >>> More
Context Free Language Question (Pumping Lemma)

as seen on Stack Overflow - Search for 'Stack Overflow'
I know this isn't directly related to programming, but I was wondering if anyone know how to apply the pumping lemma to the following proof: Show that L={(a^n)(b^n)(c^m) : n!=m} is not a context free language I'm pretty confident with applying pumping lemmas, but this one is really irking me. … >>> More

Related posts about regular-language

What's a regular language?

as seen on Stack Overflow - Search for 'Stack Overflow'
I've read that you can't parse HTML with regular expressions because HTML is not a regular language. I tried searching Wikipedia, but I didn't understand a word of what the various related articles said. Can someone explain, in simpler terms, what's a regular (or non-regular) language, and why non-regular… >>> More
deriving regular expressions from a regular language

as seen on Stack Overflow - Search for 'Stack Overflow'
Given the language below, how do i find a regular expression for the language L = {a ^n b ^m | n = 1, m =1, nm =3} >>> More
Theory of Computation - Showing that a language is regular..

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm reviewing some notes for my course on Theory of Computation and I'm a little bit stuck on showing the following statement and I was hoping somebody could help me out with an explanation :) Let A be a regular language. The language B = {ab | a exists in A and b does not exist in A*} Why is B… >>> More
generalizing the pumping lemma for UNIX-style regular expressions

as seen on Stack Overflow - Search for 'Stack Overflow'
Most UNIX regular expressions have, besides the usual *,+,? operators a backslash operator where \1,\2,... match whatever's in the last parentheses, so for example L=(a)b\1* matches the (non regular) language a^n b a^n On one hand, this seems to be pretty powerful since you can create (a*)b\1b\1… >>> More
Regular Expression for any number divisible by 60 using C# .Net ?

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi there, I need to apply validation on input time intervals that are taken in as seconds. Now i am not really good at Regular expressions. So can any body help making a regular expression that can test whether a number is divisible by 60. I was wondering if i could use to test one that check that… >>> More