New answers tagged automata
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 ...
- 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 ...
- 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 ...
- 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 ...
- 229
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
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
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
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
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
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,030
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
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 ...
- 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 ...
- 1,030
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
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
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,030
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
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
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
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
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,154
Top 50 recent answers are included