# Tag Info

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