The 2024 Developer Survey results are live! See the results

# Tag Info

Accepted

### $L'=\left \{w : w\cdot Drop_a(w)\in L \right \}$ is a regular language

Note that a word $w$ is in $L'$ iff there exist states $q\in Q, q_f\in F$ such that $q_0 \xrightarrow{w} q$ and $q \xrightarrow{drop(w)} q_{f}$, where the latter runs are runs in $A$. The first run is ...
• 3,666

### Why NFA is called Non-deterministic?

Both DFA and NFA are deterministic in the sense that they will always accept a string that is part of the language they recognize and reject it otherwise. However, when reading a same string ...
• 21

### How does a minimal DFA ensure minimal computational cost?

As Yuval commented, I also think you're taking Wikipedia too literally. The way I interpreted that sentence is as follows. Decision procedures about deterministic automata are easier compared to ...
• 3,666

### Why must 2 distinct strings go to the same state in a DFA?

Consider a DFA $A = (\Sigma, Q, q_0, \delta, F)$. As $A$ has a total transition function, that is, $\delta(q, \sigma)$ is defined for every state $q$, and letter $\sigma$, then upon reading any word ...
• 3,666

### Creating a DFA where the string should start with b and the length is 3

Hint 1: Every state in a DFA "remembers something", for example, in your attempt, the state $q_1$ remembers two things: (1) that we've just read $b$, and (2) that we've read a word of length ...
• 3,666

### Do all regular languages have a backwards deterministic FSM with one initial state and no $\varepsilon$-transitions?

General Idea: I don't there is such an automaton for all regular languages. Without $\varepsilon$-edges the amount of looping you can do is very restricted, so the idea is to show that the number of ...
• 1,467