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,678

### 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,678

### 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,678

### 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
Accepted

• 3,678
1 vote

### How is L = a^2n regular if it doesn't pass the pigeon-hole principle test?

The simplest DFA has two states S and O, every a switches from S to O and from O to S, and S is accepting. After 2n “a”s we are in state S, and after 2n+1 “a”s we are in the non-accepting state O. It’...
• 31.2k

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