24
Regular expressions using only concatenation, alternation and Kleene star describe regular languages. In contrast, extended regular expressions available in modern programming languages can describe non-regular languages. For example, (.*)\1 describes the language $\{ ww : w \in \Sigma^* \}$, which is not even context-free.
5
The answer by @YuvalFilmus is perfectly fine, and points you to the import notion of star height. But let me add a little bit more. We will show that languages of your form give a proper subset of the languages of star height one. But first, some musings what might come close to your form.
General Regular Languages
First, probably the closest form to yours ...
3
Since I see questions about the pumping lemma on this site quite often, I decided to write a bit of a longer answer hoping that it helps people "get" the PL rather than just treating it as a "plug-n-chug" tool given to us by the gods of math.
Understanding the PL
I think the best way to go about it is to basically (re-)derive the lemma.
...
1
If $x\in AA^ā$ then there are $a\in A$ and $b\in A^ā$ such that $x=ab$. Since $b\in A^ā$ then either there are $b_1,b_2,...,b_n\in A$, with $n\geq1$, such that $b=\prod_{k\in[1,n]}b_k$ or $b=\epsilon$. It follows that either $x=a\prod_{k\in[1,n]}b_k$ or $x=a$. In the first case you can write $x=\left(a\prod_{k\in[1,nā1]}b_k\right)b_n$, since concatenation is ...
1
$AA^*$ is the set of all strings consisting of a string in A, followed by zero or more strings in A, which means all strings consisting of one or more strings in A. $A^*A$ is the set of all strings consisting of zero or more strings in A, followed by one string in A, which also means all strings consisting of one or more strings in A. So both are the same.
1
See this paper for an extended discussion which includes the old Chomskyan center-embedding arguments that English, for example, is not regular.
See this answer for an argument that natural languages are not context-free and therefore not regular. Moreover, there is no agreement as to what a syntactic theory of natural languages would look like. The ...
1
In order to show that $f$ is regularity preserving, it suffices to show that $f^{-1}(U)$ is eventually periodic for $U = \{ n : n \equiv b \pmod{a} \}$, where $a$ is a prime power (here we are using the Chinese remainder theorem and the fact that the eventually periodic sets are closed under intersection).
For $f(n) = 2^n$, we consider two cases:
If $a = 2^...
1
Hint:
1
The best way is to learn is to look at examples, and see how they work.
One of the simplest "real" context-free languages is $\{\; a^mb^n \mid n = m \;\}$
Its grammar is $S\to aSb\mid \varepsilon$.
Now add in steps, the extra 3, and the more than ...
$\{\; a^mb^n \mid n = m+3 \;\}$
$\{\; a^mb^n \mid n \le m+3 \;\}$
1
Arden's theorem states that $A^*\,B$ is the least fixed point of the equation:
$$ X = A\,X\,\cup B$$
and that $A\,B^*$ is the least fixed point of the equation:
$$X = X\,B\,\cup A$$
In your case, $R = Q\,P^* = a^* (a b)^*$.
1
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$, $\...
1
You want to prove that if $\equiv_S$ has infinite index, then $L$ is not a regular language, or, equivalently that if $L$ is regular, then $\equiv_S$ has finite index. This is an immediate consequence of the following result.
Theorem. Let ${\cal A} = (Q, \Sigma, \cdot, i, F)$ be the minimal complete deterministic automaton of $L$. Then $u \equiv_S v$ if and ...
1
After a bit more thought I believe this is indeed true and that I've got a proof of it. The idea is to proceed by contrapositive and instead prove that if $L$ is regular, then $\equiv_S$ has only finitely many equivalence classes.
We can see this by pulling in Brzozowski derivatives. Given the language $L$ and any string $x \in \Sigma^*$, we define the ...
Only top voted, non community-wiki answers of a minimum length are eligible
