Hot answers tagged

2

Hint/Sketch of proof: The complementary language, i.e. language of strings which either do not start by "$010$" or are palindromes, can be shown not to be regular by using pumping lemma. It's roughly in the same proof you do when you show that the language of palindrome strings is not regular. The idea: Pick $L$ said language, $n$ as in pumping lemma. Pick ...


1

Recall that all regular langauges satisfy the pumping lemma, which we capture by the following informal proposition: $$\text{regular}\implies\text{pumping lemma}.$$ Applying modus tollens (a.k.a. contrapositive), we get $$\neg\text{pumping lemma}\implies\neg\text{regular}.$$ Therefore, to prove a language is not regular, it suffices to show that it does not ...


1

Ok, I'll tell you the answer. A string is in $S$ if and only if it consists of $1$ or more $a$'s followed by $0$ or more $b$'s and $c$'s. If you look at the strings you got that seems right, right? A formal proof will be by induction.


1

Yes, "effective" means something like the construction can be carried out in finite time. But this does not mean that it is enough that $K$ is decidable. Consider for example that we could let $$ K=\{\mathtt{a}^n\mid n\text{ is a perfect number}\} $$ and $L=(\mathtt{aa})^* $. It is easy enough to specify a way to decide $K$, but that does not make it any ...


1

HINT: For each $n\in\Bbb Z^+$ let $w_n=01(01)^n1$: $w_1=01011$, $w_2=0101011$, $w_3=010101011$, and so on. Similarly, let $z_n=(01)^n0$. Show that $w_mz_n$ is a palindrome if and only if $m=n$, and apply the Myhill-Nerode theorem.


1

Let $ S \subseteq \mathbb{N} $ not be $ RE $. Take $ L = \{ a^n \ | \ n \in S \} $. Then $ L $ is not $ RE $. You can also construct explicit examples of such sets, like $ L = \{ a^n \ | \text{ The } n^{\text{th}} \text{ Turing machine halts on all inputs} \} $. To go even further, any infinite set has subsets which are not $ RE $. Let $ A \subseteq \...


1

Your pumping lemma argument for $ L $ makes sense, with the exception that you switch between using $ p $ and $ n $ for the pumping length. The same word doesn't work for $ L' $ though - your word can be split into $ x = \epsilon, y=0, z=0^p1^p $. Then $ xy^iz = 0^{p+i} 1^p $ is in $ L' $ (since it has the prefix $ 0 $ which has more $ 0 $s than $ 1 $s). ...


1

The language $L_4$ is not context-free. Indeed, if it was, then $L_4 \cap \{a,b\}^* = \{ ww \mid w \in \{a,b\}^* \}$ would also be context-free. But it is not: see for instance this answer by Brian M. Scott.


1

Let $L = L_1 - L_2 = \{a^pb^qc^r \mid p,q,r > 0, p \not=r\}$ and suppose that $L$ is regular. Then the language $a^+bc^+ - L = \{a^pbc^p \mid p > 0\}$ would also be regular, which is not the case. Thus $L$ is not regular.


1

$0 \in L$, but not in your language $(10)^*$. Further $$ (0|10)^*(\epsilon | 1) = (0|10)^* \epsilon \,|\, (0|10)^* 1 = (0|10)^* \,|\, (0|10)^* 1 $$ E.g. $10 \in (0|10)^*$, which is in $L$ but not in your $(0|10)^*1$.


1

The string "$00$" matches the requirements but your answers doesn't permit that to happen.


1

The language the automaton accepts is supposed to consist of all strings that contain at least three as -- not only some of them. The second of the automata you show fails to accept baaa -- there's no transition that will match the initial b. Since the language accepted by the second automata does not include baaa and baaa is a string that contains at ...


1

This depends to some extent on the terminology used in your course. However a DFA, as I understand the term, must have exactly one transition from every state for each letter. This is not the case in your second example so it is not a DFA. Your second example is however an instance of a non-deterministic finite automaton. You will quite likely prove in ...



Only top voted, non community-wiki answers of a minimum length are eligible