patternMajor
Can a regular expression be infinite?
Viewed 0 times
expressioncanregularinfinite
Problem
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 ?
I know this is a trivial thing, but does the definition of regular expression includes the condition that it should be finite ?
Solution
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.
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.
Context
StackExchange Computer Science Q#47835, answer score: 24
Revisions (0)
No revisions yet.