Hi,
I am preparing contex free grammar for an exam. I couldn't understand why the language
{ a^n b^n | n>=0}
is context free but not regular. Why is it not regular? When can we say that an expression is not regular?
Thanks
+2
A:
An expression is not regular if it cannot be matched (exactly) by a regular expression or (equivalently) a finite state machine. See also context free language and regular language.
Laurence Gonsalves
2010-01-13 07:17:33
+1
A:
Well you can say it is context free because you can express it using a Context-Free Grammar. It is not regular however because a regular expression (and finite automata) can not represent that language.
ghills
2010-01-13 07:17:49
A:
Like said in previous answers, its context free because you can express it with context free grammar.
For example: S -> aSb | ε
Its not regular because you cannot express it with finite state machine nor regular expressions. You should be able to count the number of As and check that number of Bs match. This cannot be done with finite states as n could be anything
Anssi
2010-01-13 07:42:27