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

# Tag Info

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

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

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

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

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

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

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

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

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

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