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 =...


4

No, since the change from a language to its smallest prefix-free sub-language is computable. Suppose language $L$ is computable. That is, we can list all words in $L$ in nondecreasing length. Scanning the list, we will keep only the words that are not an expansion of any word that have been scanned. The list of words left, $P$, is the smallest prefix-free ...


3

Hint: replace every $d$-depth transition with a set of states and transitions that will read out $d-1$ elements, then read the last element and do the transition, and afterwards return the last $d-1$ elements back to the stack. Another hint: to "remember" the $d-1$ elements, construct a unique "path" for each unique combination of the $d-...


2

The reason that $L_1$ is context-free is that one needs to keep track of only two numbers at the same time: either $l=m$ or $m=n$. The 'or' is handled using union, we patch two languages together. The difference of the two numbers $l-m$ or $m-n$ can be stored on the stack while reading the string. Your language $L=\{a^mb^nc^n \mid m\neq n\}$ is not context-...


1

Let $Q$ be a $DFA$ recognizing $L$. To show that $\mathrm{three}(L)$ is regular, you only need to construct a $NFA$ deciding $\mathrm{three}(L)$ (this suffices, since any $NFA$ can be transformed to an equivalent $DFA$). Now, the key idea is that if the $NFA$ is reading, say, the first character $c_3$, then it can guess what two characters $c_1,c_2$ occurred ...


1

One of the possibilities is to keep the topmost $i$ symbols of the stack in the finite memory rather than putting it on the stack. Any simple symbol replacement of the topmost symbols can be performed in memory, rather than on the stack. If we push or pop symbols from/to the stack we also push or pop from the (shorthened) stack, shifting symbols from/to the ...


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 ...


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