Tag Info

Hot answers tagged

5

In a finite language there will be a maximal length of any string in the language -- call it $n$. There are finitely many possible strings of at most $n$ symbols. Construct a Turing machine with a state for each of those strings. As long as the state corresponds to a string of less than $n$ symbols it will move right and switch to a state that encodes the ...


2

Take a one-letter alphabet $\{a\}$ and let $L = \{a^{n^2} \mid n \geqslant 0 \} \cup \{a^{2n+1} \mid n \geqslant 0 \}$. Then $L^2 = a^*$, a regular language, and I let you verify that $L$ is not regular.


2

First let us define one useful notation: we say that a positive integer $w \in \mathbb{Z}$ belongs to L if $a^w \in L$. In other words, $w \in L \iff a^w \in L$. We will prove that a language that satisfies pumping lemma is periodical starting from some point. In other words, there exist numbers $s, f \in \mathbb{N}$ and a set of residues $F \subset [0..f)$ ...


2

For b), let $L_1=\Sigma^{*}$ and let $L_2$ be any non-regular language you like that contains the empty string. Then $L_1 L_2=\Sigma^{*}$. For a), let $L_2$ be the set of all strings not of the form $a^n b^n$ for $n\ge 1$. (This is clearly non-regular because its complement is non-regular.) Every string is either not of the form $a^n b^n$, or is of that ...


2

By definition, $h^{-1}(w)$ is the set: $$\{v \in \{a,b\}^* \mid h(v) = w\}$$ Depending on your definitions, this can be an abuse of notation, because $h^{-1}$ might not be a mapping. However, it is convenient to omit the inner braces in the formally more correct $h^{-1}(\{w\})$. As to the set itself: Because there is no possibility for $h$ to yield three ...


1

Your idea goes in the right direction - you just need to also keep track of the fact that you essentially "skipped" an input in the non-chosen automaton. In a nutshell, what you want is a variant product construction: Let the original automata be $A_i=(Q_i,q_i^0,F_i,\delta_i)$ for $i=1,2$. Then your NFA has set of states $Q_1\times Q_2$, with initial state ...


1

There are several problems here, though the choice of $s$ is sound. First, I suspect that you meant that $x=a^q$, though the $q$ is missing both in the definition of $x$ and later in the expansion of $xyyz$. In that case you might as well say that $x=a^{m-k}$. Next, the definition of $z$ is simply wrong: $z=bba^m$. Now the pumping lemma says that $xy^2z\in ...


1

First of all, let me state your question a little more precisely. Let $A$ be a finite alphabet and let $\sim$ be the congruence on $A^*$ generated by the relations $a \sim a^2$, for each letter $a$. Then if $u = a_1^{k_1}a_2^{k_2} \dotsm a_n^{k_n}$, where $k_1, ..., k_n > 0$ and two consecutive letters $a_i, a_{i+1}$ are always distinct, then $$ [u]_\sim ...


1

I guess you mean regular languages accepted by finite automata. Just Google one of these words: finite automaton, DFA, NFA, regular language or look at this question How to convert finite automata to regular expressions? Edit. To answer your last remark, you might be interested in this paper, which heavily relies on Stone duality.


1

HINT: $L_1\cup L_2=L_2$, and $L_1\cap L_2=L_1$. For (d), note that you can design a DFA that handles the members of any finite collection of words, like $\{\lambda,ab,a^2b^2\}$, individually, and handles all other words separately. Your use of the pumping lemma in (a) is correct.


1

HINT: With $S$ as the initial symbol, start with these productions: $$\begin{align*} &S\to aL\mid bL\mid Ra\mid Rb\\ &L\to aL\mid bL\mid X \end{align*}$$ Have $R$ do something similar to what $L$ does, and have $X$ generate the language $$\big\{x\#y:x,y\in\{a,b\}^*\land |x|=|y|\big\}\;.$$ In other words, generate excess length on one side, then ...


1

All you have to do is observe that if $m > 1$ then (continuing your proof) $$ m! < m! + m < 2m! < (m+1)! $$ On the other hand, if $m = 1$ then $k=1$ and for $i=3$ you get $$ 2! < |w'| = m! + 2k = 3 < 3! $$ Either way, $w' \notin L$ because every word in $L$ has factorial length, but this contradicts the pumping lemma. Your notation is a ...


1

Your work for (a) is fine, but your regular expression is wrong: its last term matches $aaaaa$, for instance, which is not in $L$, and none of it matches $bab$, which is in $L$. It looks as if you tried to generate it from the transition graph and made quite a few mistakes; in particular, it looks as if you forgot to keep track of which states in the ...


1

$\{a^nb^m:m,n\ge 0\}$ is a regular language, but it is clearly not finite. It contains one word for each ordered pair $\langle m,n\rangle\in\Bbb N\times\Bbb N$, so it has the same cardinality as the set $\Bbb N\times\Bbb N$ and is therefore countably infinite. Every finite language is regular, but there are many regular languages that are not finite. Indeed, ...


1

$r_1$ and $r_2$ are correct, also I'd write $r_2$ shorter as $(a+b)^*(aa+bb)(a+b)^*$. $r_3$ is wrong, note that $bbaa \in L_3$ isn't matched by $r_3$, $r_3$ matches the words which contain $aa$ before $bb$, you can fix this by writing $$ (a+b)^*\bigl(aa(a+b)^*bb + bb(a+b)^*aa\bigr) (a+b)^* $$ that is, just adding the other case. $r_4$ is correct, here ...



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