0
$\begingroup$

Is it possible to have a regular expression from a language (that has strings of infinite length) which it describes ?

$\endgroup$
  • 1
    $\begingroup$ Your question is not clear enough. Could you try rephrasing it, or perhaps add an example of what you mean? $\endgroup$ – Shaull Sep 3 at 7:56
  • $\begingroup$ A language can be defined by a regular expression iff it is regular. $\endgroup$ – Yuval Filmus Sep 3 at 11:35
  • $\begingroup$ No language contains strings of infinite length. $\endgroup$ – vonbrand Sep 3 at 13:24
  • $\begingroup$ Do you mean a language $L$ consisting of strings, at least one of which, $s_i$ interpreted as a regular expresssion exactly describes $L$? $\endgroup$ – Rick Decker Sep 3 at 15:10
1
$\begingroup$

Your question is unclear. However "a language (that has strings of infinite length)" cannot exist. By definition a language only contains words of finite length.

Let $\Sigma$ be a (finite) alphabet and $\epsilon$ denote the empty word. A language is a subset of $\Sigma^*$, where $\Sigma^*$ is defined as $\Sigma^* = \cup_{i=1}^{\infty} \Sigma^i$, $\Sigma^0 = \{ \epsilon \}$, and $\Sigma^i = \{xy : x \in \Sigma^{i-1}, y \in \Sigma\}$ for $i>0$.

As you can see, a string of infinite length does not belong to any $\Sigma^i$ and therefore it belongs to neither $\Sigma^*$ nor to any of its subsets.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Don't know exactly what you mean, but a is an element of L(a). Actually the only element of L(a). (while a* is not an element of L(a*) because none of the elements contain the symbol *).

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.