New answers tagged

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