# Tag Info

5

If $p$ is a proposed pumping length, let $q > p$ be prime, and consider the string $w = a^qb^{(q^2)} \in L$. (Clearly $|w| = q+q^2 \geq p$.) Let $w = xyz$ be a decomposition such that $y \neq \varepsilon$, and $|xy| \leq p$. In follows that $y = a^k$ for some $1 \leq k \leq p < q$, and so "pumping" it zero times results in the string $$xy^0z = xz ... 4 The answer is yes. Let v(u) be the binary value of a binary word u. By definition,$$L = \{u \in \{0,1\}^* \mid 0^{v(u)} \in R\},$$where R is some regular language. First of all, since R is regular, S = R \cap 0^* is also regular and$$ L = \{u \in \{0,1\}^* \mid 0^{v(u)} \in S\}.  A regular language on the alphabet $\{0\}$ is semilinear, that ...

2

Your given regular expression is : $(aa)^*a(bb)^*$. Regular language is : $\{a^{2m+1}b^{2n}|m,n\ge 0\}$ Your given NFA is for above language : So, the transitition table for above NFA is : +-------+-----+---+ | State | a | b | +-------+-----+---+ | A | B,C | | | B | | D | | C | A | | | D | | B | +-------+-----+---+ ...

2

Every regular grammar which contains a rule of the form $A \rightarrow aB$ (reachable from the start symbol) has an equivalent ambiguous regular grammar. Just take a new non-terminal symbol, $D$, add the rule $A \rightarrow aD$, and for each rule with $B$ as the left symbol add a new rule obtained by replacing each $B$ in that rule with $D$. For example, ...

1

There do indeed exist ambiguous regular grammars. Take for example $S\rightarrow A~|~B$ $A\rightarrow a$ $B\rightarrow a$

1

Your question can indeed be solved in a short way using the closure propeties of regular languages. Since you just ask for a kick in the right direction, I just give you a hint for the first (and more important) step. I will give you more details only if needed. Hint. If $L$ is regular, then for each regular language $K$, $L \cap K$ is also regular. Try to ...

1

It's pretty clear from inspecting the DFA that $L_3 = L(M)$: from $q_0$ we do some sequence of $0$-selftransitions (going throught the loop), and then we must see a $1$ to go to $q_1$, which is the only terminating state. We could stop then (so then we just have $0^\ast 1$ as the input sequence), or we do excursions to $q_0$ or $q_2$, and so we either have ...

1

No. Call a language lacunary if it is infinite and the gaps between the distinct lengths of words goes to infinity; for example, the language of words whose length is square. By the pumping lemma, no lacunary language is regular (or context-free), and every infinite subset of a lacunary language is lacunary.

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