Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

New answers tagged

1 vote

determining the relationship between two regular languages using the myhill nerode theorem

No, the statement is not true. The language defines the equivalence classes, but not the other way around. Each class can be totally within or totally outside the language. So with several classes we ...
user avatar
  • 27.2k
1 vote

Benefit of Petri Net Transition as Separate Object

In my experience, the duality of Petri nets is a great strength. It forces us to specify the potential events or actions in a system (the transitions), as they may happen to individual items (the ...
user avatar
  • 4,631
0 votes

finite automata that accepts integers divided by 3?

Hint: If the remainders of $n$ by $3$ are $0, 1, 2$, then the remainders of $n$ followed by zero (i.e. $2n$) are $0, 2, 1$, and the remainders of $n$ followed by one (i.e. $2n+1$) are $1,0,2$. This ...
user avatar
  • 3,437
0 votes

finite automata that accepts integers divided by 3?

We want to design a Deterministic Finite Automaton (DFA) that accepts Binary Representation of Integers which are divisible by 3. Now, by accept, in layman terms, we can say that when we are done ...
user avatar
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
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
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
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
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
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
0 votes

What exactly is pumping length in pumping lemma?

A regular language has a finite state machine, and therefore it has a finite state machine with a minimum number of states n. If we examine the first n letters of an input string, there are n+1 states ...
user avatar
  • 24.9k
0 votes

Is ε a part of alphabet or property of alphabet and NFA in FA

There's a difference between how an NFA is represented and how it computes. Three common representations of an NFA are its state transition diagram, the tabular representation, and a description of ...
user avatar
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

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

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

Top 50 recent answers are included