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 ?
$\begingroup$
$\endgroup$
3
asked Oct 4, 2015 at 0:39
-
3$\begingroup$ You already answered your own question: if REG $\subsetneq$ CFL, such terms can not be regular expressions. $\endgroup$– RaphaelCommented Oct 4, 2015 at 10:30
-
1$\begingroup$ Just a side note: if we drop the requirement of DFA/NFA being finite, we can build an automaton to accept $\{0^n1^n\mid n\geq0\}$. $\endgroup$– user23039Commented Oct 4, 2015 at 20:43
-
3$\begingroup$ As a point of terminology, the word 'automata' is the plural of 'automaton'. There is no word 'automatas' -- you can't make it more plural than it already is. (automata's is correct as a possessive but not as a plural) $\endgroup$– chasly - supports MonicaCommented Oct 4, 2015 at 21:53
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
5
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.
-
5$\begingroup$ I love this answer, because it not only says that infinite regular expressions are different, but that the concept on the whole isn't meaningful. $\endgroup$ Commented Oct 4, 2015 at 2:27
-
$\begingroup$ A more succinct statement of the point I buried in my second paragraph, and therefore clearer. $\endgroup$– DavislorCommented Oct 4, 2015 at 16:00
-
$\begingroup$ But it does conclude with a pure tautology. Why don’t we consider all languages regular, then, if they have this form? The things we do with regexes no longer work. We can’t build a state machine by an inductive algorithm because it never finishes and has infinite states. We can’t compare to everything in the list and reject if nothing matches. And we can’t physically represent the list anyway. (The lists we can generate by computer are the decidable languages.) We can prove stuff using the fact that every language has this form, but not the kind of stuff we know about regexes. $\endgroup$– DavislorCommented Oct 4, 2015 at 17:29
-
$\begingroup$ @jmite "isn't meaningful" or a special case? $\endgroup$– BARCommented Oct 4, 2015 at 20:39
-
$\begingroup$ @BAR Isn't meaningful, as in the class of languages over $\Sigma$ described by infinite regular expressions is just $2^{\Sigma}$ i.e. the set of all languages. We don't get a class of languages the way you do with finite REs, CFGs, or even Turing Machines. $\endgroup$ Commented Oct 4, 2015 at 21:19
$\begingroup$
$\endgroup$
3
Yes, it must be finite. Imagine you have that infinite set of possible matches, and your input is 011. Would you ever be able to reject it? Would you ever run out of matches to check?
Is there any language that, by that definition, would not be regular? What about the set of all pairs of programs and inputs such that the given program halts on the given input?
Now, if you had a program that enumerated the strings in a language in lexicographical order—
Update
To clarify a bit based on feedback in the comments, the reason not every language of this form is regular is by definition. If, for example, you look up the proof of Kleene’s theorem, it depends on the fact that a regular expression must be finite to prove that it generates a finite state machine.
Why do we define “regular” language that way? Because every formal language is a subset of the strings on an alphabet, and every set of strings can be expressed as a union of singletons, so if we called any set of strings a “regular” language, regular language would just be a synonym for language. That’s not a very useful definition, especially since we can’t actually implement it in hardware or software. We can’t store an arbitrary infinite list anywhere or build an infinite-state machine.
As I hinted, though, if you have a way to enumerate all the strings in a language in order, you can build a decider from that (accept when you see that exact string, reject when you encounter a string that comes after the one you’re looking for) and vice versa (for each string in order, run it through the decider and output it if and only if it’s accepted). So, if we considered every enumerable language regular, every decidable language would be “regular” and we would need a new term for the languages recognized by finite state machines and their equivalent encodings as finite expressions.
-
1$\begingroup$ This answer is wrong. The fact alone that some representation of a language does not lend itself to building an algorithmic decider in a naive way does not imply that this representation is wrong; there could be other approaches. In fact, every decidable language has a representation of the form sasha proposes! In short, you are committing the "I can't see how, so it has to be impossible" fallacy. $\endgroup$– RaphaelCommented Oct 4, 2015 at 10:34
-
$\begingroup$ @Raphael: Please consider the implications of your statement, ”every decidable language has a representation of the form Sasha proposes!” That is, in fact, the point I was making in my answer. The question was, are all languages of this form defined as regular? Well, is every decidable language regular? (And, as I showed, some undecidable ones too?) Would that be a useful definition of “regular?” $\endgroup$– DavislorCommented Oct 4, 2015 at 14:33
-
$\begingroup$ Furthermore, far from fallacizing that a decider for an infinite list of the strings can’t be done, my last sentence was a hint at how it could be done: if the list of strings is well-ordered, you can reject one as soon as you encounter a string past it in the ordering. However, a finite state machine cannot do this because it cannot represent all the states of having compared to each string in the infinite list, and neither can regular expressions. If they could, they would be powerful enough to recognize all decidable languages. $\endgroup$– DavislorCommented Oct 4, 2015 at 14:38
$\begingroup$
$\endgroup$
1
Suppose regular expressions were allowed to be infinite.
Thus language defined by {ϵ}∪{01}∪{0011}... will be regular. For every regular language there exists a NFA. One way to get this NFA would be to have individual NFAs for each of {ϵ},{01},{0011}... and combine them using ϵ transitions. Since there are infinite distinct regular expressions, we will need infinite sub-NFAs to be combined. However NFA can have only finite number of states (definition of NFA).
Thus there exists no NFA that can define language defined by union of infinite regular expressions, which implies the language is not regular.
Thus there is no regular expression which can define same language as the language defined by union of infinite regular expressions.
Thus regular expressions can have only finite expressions.
-
$\begingroup$ Your "infinite regular expressions" then define another class of languages, not regular laguages. In fact, they are able to define any language whatsoever, and that is utterly uninteresting (they aren't finite, thus hard to work with; and they can do anything, thus nothing to study in terms of limitations). $\endgroup$– vonbrandCommented Oct 9, 2015 at 10:16