# Tag Info

## New answers tagged formal-languages

Accepted

### Is my DFA optimal?

Seems mimimal to me. You can actually prove that the DFA is minimal by applying the Myhill-Nerode theorem. Two states $p$ and $q$ can not be merged if they can be "distinguished" in the ...
• 28.2k

### Is the reversal of a minimal DFA also minimal?

The "standard" example that shows that the NFA to DFA construction is exponential in size also works for reversal. The DFA for $\{0,1\}^*1\{0,1\}^n$, the $n+1$-st symbol from the right is $1$...
• 28.2k

Accepted

• 28.2k
Accepted

### pumping lemma length restrictions clarification

First, for the sake of preciseness, note that the Lemma says that for every regular language $L$, there exists a constant $m\ge 1$, such that for every word $w\in L$... [what you wrote]. That is, the ...
• 16.5k

### Is LR(1) closed under union?

A simple example is $$L_1 = \{a^i b^i c^j \mid i,j\ge 0\}$$ $$L_2 = \{a^i b^j c^j \mid i,j\ge 0\}$$ Clearly, both languages are $LR(1)$. (Indeed, they are $LL(1)$.) But their union is inherently ...
• 11.4k
Accepted

### minimal DFA transition function clearification

$\widehat{\delta(q, a)} = \hat{\delta}^{}(\hat{q}, a)$ The equality above is the definition of $\hat\delta$, given $\delta$. Let us paraphrase item 3. For each transition rule of $M$ of the form  ...
• 35.3k
Accepted

### Prove or disprove: deterministic Turing machine equivalence Nondeterministic Turing machine such that word

Take a look at Micheal Sipser Introduction to the Theory of Computation 3rd edition pages 178 and 179. In short, the proof uses a three-tape turning machine $D$ (which is equivalent to an ordinary ...
• 170
1 vote

### How to recognize all halting states of a turing machine?

A turing machine is defined as a 7-tuple $M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$. The set $F$ in the tuple is the set of final states or accepting states. So any other states other ...
• 170
1 vote
Accepted

No. $\{a^nb^mc^k\mid n>m>k\}$ is not the complement of $\{a^nb^mc^k\mid n\le m\le k\}$, for two reasons. (1) The negation of the logical statement "$P\land Q$" is not "$\lnot P\... • 28.2k 1 vote ### Is$\{a,b,c\}^* \setminus \{a^nb^mc^k \mid n \leq m \leq k\}$context free? You ask: Isn't that also the complement of the language? Here that refers to$L' = \{a^n b^m c^k \mid n > m > k\}$but I'm not sure what the language refers ... • 24.2k 1 vote Accepted ### Extended transition function in NFA You can show that all states in the set on the left hand side are included in the set on the right hand side, and vice-versa.$s \in \delta_N^*(q, w)$if and only if there is some path$\pi(q,s,w)\$ ...
• 24.2k

Top 50 recent answers are included