Problem Detail: I know that languages which can be defined using regular expressions and those recognisable by DFA/NFA ( finite automata ) are equivalent. Also no DFA exists for the language ${0^n1^n|n ge 0}$. But still it can be written using regular expressions ( for that matter any non-regular language can be ) as ${ epsilon } cup {01} cup {0011}……$ . But we know that every language that has a regular expression has a DFA that recognises it ( contradiction to my earlier statement ). I know this is a trivial thing, but does the definition of regular expression includes the condition that it should be finite ?
Asked By : sashas
Answered By : Ran G.
If regular expressions were allowed to be infinite, then any language would have been regular. Given the language $L={w_1, w_2, ldots}$, we can always define the regular expression $R = w_1 + w_2 + cdots$, which exactly defines $L$.
(Example: the regular expression $R_1 = epsilon+0+1+00+01+10+11+cdots$ defines $L_1={0,1}^*$.) We know that some languages are not regular, so this shows that infinite regular expressions describe a larger class of languages than finite regular expressions.
(Example: the regular expression $R_1 = epsilon+0+1+00+01+10+11+cdots$ defines $L_1={0,1}^*$.) We know that some languages are not regular, so this shows that infinite regular expressions describe a larger class of languages than finite regular expressions.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/47835
