4
votes
If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$
Take a DFA $(Q,\Sigma,\delta,q_0,F)$ accepting $\mathcal{L}$. We can associate each word $x \in \Sigma^*$ with a function $\delta_x\colon Q \to Q$ given by $\delta_x(q) = \delta(q,x)$. In other words, ...
- 269k
4
votes
Accepted
DFA for the language of non-empty words that are no longer than $2^6$
Suppose the minimal DFA $(Q, \delta, q_0, F)$ contains strictly less than $2^6$ states. Then there exists a state $q$ and two words $u$, $v$ such that $|u| < |v| \leqslant 2^6$ and $\delta(q_0, u) =...
- 7,127
3
votes
If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$
Idea: Suppose we have an NFA $(Q, \Sigma, \Delta, I, F)$ for $\mathcal{L}$. To build an NFA for $\text{SW}(\mathcal{L})$, our plan is to make a separate copy of the states of the NFA for each ...
- 5,144
3
votes
Accepted
How to convert AFA to ε-NFA / NFA / DFA?
The construction yields a nondeterministic NFA $A'$ that is equivalent to the original alternating AFA $A$.
The states of the new automaton are sets of states of $A$, just as in the classic ...
- 27.2k
2
votes
Accepted
Converting Deterministic Finite Automata to Regular Expression
Jacques Sakarovitch studies the outcome of the various algorithms.
See his paper The Language, the Expression, and the (Small) Automaton (CIAA 2005. LNCS 3845), where some results are summarized that ...
- 27.2k
2
votes
Accepted
Converting Regular Expression to Finite Automata
The construction that you show from the book of Sipser is known as Thompson’s construction, building a nondeterministic automaton with $\varepsilon$-transitions. Those empty transitions can be removed ...
- 27.2k
2
votes
Myhill–Nerode equivalence classes for the language $b^ia^{5j}$
The Myhill-Nerode relation with respect to a given language $L \subseteq \Sigma^*$ is an equivalence relation on $\Sigma^*$ and hence gives a partition of $\Sigma^*$. Because this is a partition, the ...
- 1,005
2
votes
Myhill–Nerode equivalence classes for the language $b^ia^{5j}$
In order to check that these are the correct classes, you need to check three things:
Any two words in the same class are equivalent.
Any two words in different classes are inequivalent.
Every word ...
- 269k
2
votes
Accepted
What exactly is pumping length in pumping lemma?
The pumping length $n$ must be assumed to be arbitrary - you can't fix it to be a particular value. The pumping lemma is used to prove that a given language is nonregular, and it is a proof by ...
- 1,005
1
vote
A language that is either fully accepted by synchronised DFAs or not at all
A synchronizing word $w$ has the property that there is a single state $q$ of the DFA, such that for every state $s$ it holds that $\delta(s,w)=q$. That is, after reading $w$ you end up in $q$, ...
- 16.2k
1
vote
If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$
If $L$ is a language of $A^*$ and $u, v$ are words, let
$$
u^{-1}Lv^{-1} = \{ x \in A^* \mid uxv \in L \}
$$
It is a well-known fact that if $L$ is regular, then every language $u^{-1}Lv^{-1}$ is ...
- 5,925
1
vote
What exactly is pumping length in pumping lemma?
When using the pumping lemma, you do assume such $p$ exists, assuming that the language is regular. This $p$, no matter what it is, should exists since it is the number of states for the DFA of the ...
- 1,257
1
vote
Accepted
Language generated by $S \to aAb|Sb$, $A \to aAb|ab$
Start by showing that $L(A)$ (the language generated by the grammar if the starting symbol is $A$) is $L_A = \{ a^n b^n \mid n \geq 1 \}$. You prove this by double inclusion:
In order to prove that $...
- 269k
1
vote
When is a grammar ambiguous or When is a grammar not ambiguous?
That grammar as presented (with the addition of the production $A\to a$) is certainly ambiguous, regardless of what the site you copied it from says. Your work demonstrates that, and it can easily be ...
- 11k
1
vote
What exactly is pumping length in pumping lemma?
The "Pumping Length" "n" exists because you can write a finite automata that classifies all strings up to a fixed, finite length in any way it wants to.
Your finite automata can ...
- 785
1
vote
Is ε a part of alphabet or property of alphabet and NFA in FA
In the definition of $\Sigma_\epsilon$, $\epsilon$ is a letter (which must not belong to $\Sigma$).
Elsewhere, $\epsilon$ is the empty word.
To avoid confusion, you can use different symbols for the ...
- 269k
Only top scored, non community-wiki answers of a minimum length are eligible