New answers tagged regular-languages
0
Suppose that $w = ncm$, where $n \neq m^R$, say $n$'th $i$-th letter from the left, $\sigma$, differs from $m$'s $i$-th letter from the right, $\tau$. Then
$$
w \in \Sigma^{i-1} \sigma \Sigma^* c \Sigma^* \tau \Sigma^{i-1},
$$
where $\Sigma = \{a,b\}$. Conversely, every $w$ of this form is in your language. You take it from here.
0
This answer is for the original version of the question, in which "$k$" was missing.
Your language contains all non-empty words. Indeed, if $w \neq \epsilon$ then you can write $w = nm$, where $m = \epsilon$ and $n = w \neq \epsilon = m^R$. In contrast, if $\epsilon = nm$ then $n=m=\epsilon$ and so necessarily $n=m^R$.
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:
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 ...
0
I'll explain my thought process behind thinking about this problem here:
-> With inequalities, I first think at the equality constraint. So I assume n = m+3
-> Now, n is always 3 more than m.
-> I split the problem further. I think to myself okay, let's have one production handle equal production of a and b.
-> How many more b's do we need after ...
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 \;\}$
0
As you mention, if $n$ was fixed, then this is not too difficult to prove.
So, the idea would be to show that in fact, $n$ can be bounded a-priori, depending only on $A$, and not on $x$.
To this end, consider some word $x\in \Sigma^*$, and suppose $x^m\in A$ for some $m$.
Let $k$ be the number of states in some DFA $D$ for $A$ (e.g., minimal DFA). Suppose $m&...
0
Assume the language is regular, i.e., there is an automaton that recognize the language with a finite set of states. Therefore there are $i \neq j$ such that processing $a^{i +1}$ and $a^{j + 1}$ reach the same state X. Processing $4i + 2$ b's in state X always ends up in the same state Y. State Y must be accepting because $a^{i + 1} b^{4i + 2}$ is in the ...
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)^*$.
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
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 ...
0
(a) Let $\Sigma$ be the alphabet of $L$ and $\Sigma^*/\equiv_L$ the set of equivalence classes of words over $\Sigma$ according to the equivalence relation $\equiv_L$. Define the DFA to have one state for each element of $\Sigma^*/\equiv_L$ (we could think of the states as the classes themselves). Define the initial state to be the class of the empty word $\...
0
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 *).
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
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 ...
1
The basic idea is that if a regular language is infinite, then it contains a word of infinite length. Indeed, the pumping lemma shows that the set of lengths of words in the language contains an arithmetic progression, and every arithmetic progression contains a composite integer.
We can check whether the language accepted by an NFA is infinite as follows:
...
1
(This is an attempt to an answer, I hope the details are right.)
Your language consists of all strings in $(aa+bb)^*$ with an even number of $bb$.
We are allowed to use complementation, so we start by looking at the complement of the language. I think we can split the complement into two (overlapping) parts
strings not of the form $(aa+bb)^*$, that language ...
0
Let's recall the Pumping Lemma statement:
For all regular language $ L $, exists a positive constant called $ p $ (i.e. $ p \geq 1 $) such that every string $ w $ in $ L $ with length $ |w| \geq p $ exist strings $ x, y, z $ such that $ w = xyz $ and that statisfying the following conditions:
$ |y| \geq 1 $
$ |xy| \leq p $
$ xy^iz \in L, \: \forall i \geq ...
3
Here is a simple example. Take any non-regular language $N$ contained in $(aa)^+$ and consider the language $L = 1 + a(aa)^* + N$. Then $L$ is not regular since $L \cap (aa)^+ = N$ is not regular.
On the other hand, $L^2 = a^*$ is regular.
3
$(a^+b \mid b^+a)^*$. I am not sure there is a "simple" description of your language in plain English, but directly from the regex you get that it is the language that has the empty string and all strings that can be partitioned in such a way that each part is either multiple $a$'s (at least one) followed by one $b$, or vice versa.
In my opinion ...
5
Your claim is false. Indeed, it is equivalent to prove that if a language $L$ is not regular, then also $L^2$ is not regular, but this is not true. Here Yuval Filmus gives (possibly) two examples of a non regular language whose "square" is regular, namely $L = \{ 1^p \mid p \text{ is an odd prime}\}$, under the Goldbach conjecture, and $L' = \{ 1^...
7
Nice question! This is a very nontrivial problem involving regular languages.
First of all: no, you cannot run an automaton on every substring of a string skipping other letters, you are supposed to run the automaton only once on the target string.
In this case it is simpler to reason on the complementary of the given language, namely on
$$L^C = \{ w \in (...
Top 50 recent answers are included
