New answers tagged regular-languages
2
In fact, every non-trivial language is $\text{R}$-hard. That is, every decidable language is reducible to every non-trivial language. Indeed, let $A$ be a decidable language, and let $B$ be a non-trivial language. A reduction from $A$ to $B$ operates as follows. On input $x$, check whether $x\in A$ (this can be done as $A$ is decidable), then:
if $x \in A$, ...
0
If you choose $k = 2$ then, writing $|y| = m$, we get
$$ xy^2z = 0^{2^n+m}. $$
Since $1 \leq m \leq n$, we have
$$ 2^n < 2^n+m \leq 2^n+n. $$
Cantor's theorem shows that $n < 2^n$, and in particular,
$$ 2^n < 2^n+m < 2^{n+1}. $$
Therefore $xy^2z \notin L$.
Let me take this opportunity to mention another misconception. There are some non-regular ...
1
Just to make a more precise argument according to the definition below:
Myhill-Nerode Theorem: Given a language $ L \subseteq \Sigma^* $, Suppose $$ \forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^*
,L(xz) \neq L(yz)) $$ where S is an infinite set. Then L is not a
regular language.
For the given problem, We have $L(w) =\{ 0^k | k = 2^n, n \...
1
The answer is no. Every finite language is regular, and thus decidable. Therefore the existence of a finite language $L$ in $ \text{RE} \setminus \text{R}$ is impossible. However, note that there languages $L$ in $\text{RE}\setminus \text{R}$ (e.g., $Halt_{TM}$), and by what we have seen previously, such languages have to be infinite.
5
You cannot use the pumping lemma to show that a language is regular. The pumping lemma gives a property of regular languages: if $L$ is regular then $L$ can be "pumped". You can use this to show that $L$ is not regular: if $L$ cannot be pumped, then it is not regular. But you cannot use it to show that $L$ is regular: if $L$ can be pumped, it doesn'...
3
McCloskey gave such an algorithm in his paper An $O(n^2)$ Time Algorithm for Deciding
Whether a Regular Language is a Code. Given an NFA on $n$ states, his algorithm runs in time $O(n^2)$. Since a regular expression of length $n$ can be converted to an NFA with $O(n)$ states in linear time, McCloskey's algorithms runs in quadratic time even when given a ...
1
For $\sigma \in \Sigma$, let $f_\sigma$ be the indicator function of $L_{\epsilon,\sigma}$, let $f$ be the indicator function of $L$, and let $b$ be the indicator of $\epsilon \in L$. If $w = \sigma_1 \ldots \sigma_n$ then
$$
f(w) = f_{\sigma_1}(\sigma_2 \ldots \sigma_n) \oplus f_{\sigma_2}(\sigma_3 \ldots \sigma_n) \oplus \cdots \oplus f_{\sigma_n}(\epsilon)...
0
Your language consists of all strings with an even number of $a$'s and an odd number of $b$'s. How do we construct a regular expression for such a language?
Let us assume for starters that the word starts with $bb$. Thus, it has the form
$$
bba^{n_1}ba^{n_2} \ldots ba^{n_m},
$$
where $m$ is even and $n_1+\cdots+n_m$ is even. This suggests grouping the $b$'s ...
2
I don't see how the hint could be useful in applying the pumping lemma except from the fact that there are infinitely many prime numbers. So you start by a picking a word $w$ of the form $a^r$, where $r$ is a prime that is greater than the pumping constant. Then, think how many times you need to pump in order to get a word of the form $a^k$, where $k$ is non-...
2
You don’t need any code. If S is any set of integers such that the difference between neighbouring elements becomes arbitrary large, then $\{a^k: k \in S\}$ is non-regular.
1
Note that your grammar is regular. Quoting from wikipedia:
A grammar is regular when no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side.
Every regular grammar corresponds directly to a nondeterministic finite automaton, so we know that this is a regular language.
In theory, ...
0
It seems to me that you may simply consider the automata with states S, A, B, C and exit state X, and with the following transitions:
S -a-> A
S -b-> C
S -b-> X
A -a-> S
A -b-> B
B -a-> C
B -b-> A
B -a-> X
C -a-> B
C -b-> S
Right?
0
The language $L$ is not regular. One might think $L$ is regular as it is tempting to think that the number of 010s and the number of 101s in a word are dependent. Yet, as explained by @gnasher729, this is not the case because occurrences of 010 and 101 can be far from each other. It is a bit challenging to prove non-regularity of $L$ using the pumping lemma ...
2
Let $\Sigma$ be your alphabet. You want to design a Turing machine $T$ such that, given any word $w \in \Sigma^*$, $T(w)$ accepts if and only if $w \in A / B$. Notice that since you only want to prove that $A/B$ is semi-decidable, $T(w)$ is not required to reject when $w \not\in A / B$.
Since $A$ and $B$ are decidable, you know that there are two Turing ...
0
I think it might be useful to understand where the pumping lemma comes from and how it can be proven.
If a language $L$ is regular, there exists a DFA that recognizes it$^1%$.
Let $p$ be the number of states in the DFA.
As a word passes through it, the automaton goes through a sequence of states, as each symbol is consumed.
For a word $w$, if $|w| \ge p$, ...
3
You said:
If I understand correctly, $x$ and $z$ are basically anything on the 2
sides of the string $y^p$ that we're pumping and thus can be anything
in 𝐿.
This is not true. The pumping lemma suggests that for every long enough word $w$ such that $w\in L$, there is a partition of $w$ into three words $w = xyz$ such that the three conditions of the lemma ...
0
The condition $|xy|\leq p$ requires that the selected substring $y$ to be pumped is not too far from the start of the string.
Consider the language $L = \{x |x \in \{0,1\}^* x\ has\ equal\ number\ of\ 0's\ and\ 1's \}$ which can be shown to be a non-regular language via the pumping lemma. To show that this is not regular the usual example string used is $0^...
0
You almost got it Right in the comments, so I will give you the last push along with one way to think about it.
In the right automaton: the language of the automaton is simply $0\cdot L(q_1)$, where $L(q_1)$ is the set of words that can be accepted from $q_1$. Its not hard to see that a word $w$ is accepted from $q_1$ iff it $w$ is the empty word $\epsilon$,...
2
I am afraid that there is no better general result than the obvious one.
Assume that $\mathcal K$ and $\mathcal L$ are two families of languages with $\mathcal K\subset \mathcal L$ such that $\mathcal L$ is closed under the operation $\circ$. Then for $K\in\mathcal K$ and $L\in \mathcal L$ we have $K\circ L\in \mathcal L$.
This is obvious, as both $K,L\in \...
2
Here are the first few words accepted by the DFA on the right:
$$
0 \\
00 \\
000,010 \\
0000,0010,0100,0110 \\
00000,00010,00100,00110,01000,01010,01100,01110
$$
The DFA on the left accepts a subset of these words. Here are the words it does not accept:
$$
010 \\
0010,0100 \\
00010,00100,01000,01110
$$
Perhaps you can use these lists to obtain a guess on the ...
1
Option 1: the word is in the language and it is of length $\geq n$, yet there is no guarantee that pumping it yields a contradiction. That is, the word can be used in the pumping lemma, but its not a good choice for proving non-regularity. Indeed, if $\text{LONGERB}$ is regular, then we know that there is a partition of $abab^{n+1}$ to three words, $xyz = ...
Top 50 recent answers are included
