4

If you consider the language over $\Sigma = \{a, b\}$ defined by the set of words that contain a $a$ in the $n$-th position before the end, or formally: $$L_n = \{uav\mid u,v\in \Sigma^*, |v| = n\}$$ Then $L_n$ is recognized by a NFA with $n+1$ states (quite simple to find), but the minimal DFA has $2^n$ states. To prove that, suppose that there is a DFA $A =...


2

Let $h\colon \Sigma \to \Sigma^*$ be the homomorphism given by $h(\sigma) = \sigma\sigma$. Then $L’ = h^{-1}(L)$. Now use the well-known fact that regular languages are closed under inverse homomorphism. Equivalently, start with a DFA for $L$, and modify the transition function so that whenever the new DFA reads a symbol $\sigma$, it simulates the old DFA ...


2

The solution provided is pretty concise. "First, $N$ guesses the state $q_1$ that it is in just before it reads the first symbol of $x$ and the state $q_2$ that it is in just after it reads the last symbol of $x$." That means $N$ is the union of $|Q|^2$ $\text{NFA}$. (That means, running $N$ will be the same as running all those $\text{NFA}$s. $N$ ...


1

For $A\cong_0 B$, consider $\mathcal{A}_A$ and $\mathcal{A}_B$ two automata that recognize $A$ and $B$ respectively. Construct $\mathcal{A}'_B$ where you replace $1$-transitions in $\mathcal{A}_B$ with $\varepsilon$-transitions and add a $1$-transition loop on each state. Now, the product automaton between $\mathcal{A}_A$ and $\mathcal{A}'_B$ should ...


1

Another way to look at it: "Pumping length p" means that if you take a state machine, then any word w in the language with a length ≥ p must have re-entered the same state after at processing at most p characters of the input. That's not true with p = 2; 01 is in the language but doesn't require re-entering the same state within the first two ...


1

Given a language $L$, its pumping length is the minimum $p$ for which the following holds: Every word $w \in L$ of length at least $p$ can be decomposed as $w = xyz$ such that $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i$. Showing that a particular word can be pumped isn't enough — you have to show that all words in the language of length ...


1

When you want to prove your construction correct you have to be precise in your construction. The new automaton has the same states, and the same initial and final states as the original one. Then, as you suggest, for every pair of consecutive edges with the same label in the original automaton, the new automaton will have one edge with that label from the ...


1

Your question unfortunately doesn't have a simple answer. The best I can do is go over the proofs and point out where they fail when trying to apply them to the other class. Regularity of the language generated by a CFG The proof that regularity of the language generated by a CFG is undecidable is very similar to the proof that universality of the language ...


1

Structurally the classes CFL and DCFL have very different closure properties. CFL are closed under union, but not under complement. DCFL are not closed under union, but closed under complement. The undecidability of regularity for CFL is usually obtained from two properties of the context-free languages: (1) they are closed under union, and (2) universality, ...


1

The language of a right-regular grammar is certainly deterministic, because the grammar can be written as an NFA and any NFA can be mechanically transformed into an equivalent DFA using the subset construction. However, the grammar may well be ambiguous (i.e. capable of producing multiple parse trees for the same input.) That's the case for the grammar you ...


1

This answer assumes that by substring you mean consecutive substring. There is no need to use the power of NFAs. You can construct a DFA which remembers the following information: The last symbol seen (either $0$, $1$, or blank). The parity of number of occurrences of $01$ seen so far. Maintaining the last symbol seen is easy. If the last symbol seen is $0$...


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