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, ...
user avatar
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) =...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar

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