As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [finite-automata]

Questions about finite automata, an elementary automaton model with finite memory. It is equivalent to regular languages and the basis for many more complex models.

1,702 questions
Filter by
Sorted by
Tagged with
67 views

### Simple description of the LR(0) table generator algorithm?

I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think &...
765 views

### When converting a epsilon NFA to NFA to DFA, how to handle the start state?

Let's say, initially we have an epsilon NFA in which the start state, say state 1, has epsilon transition to state 3 We know when converting from epsilon NFA to NFA, we apply the following formula for ...
218 views

### Conversion of epsilon NFA to DFA, handling epsilon transitions

I am reading Michael Sipser's "Introduction to theory of computation" 3rd edition, page 55 - 56, the topic "equivalence of DFAs and NFAs" Case 0: Michael Sipser asks us to handle ...
144 views

### Automata: Are there algorithms to judge whether two automata are isomorphic?

When I want to judge whether two regular forms represent the same language, I have learned the next method: create the (non-deterministic) finite-state automata which accepts the language the given ...
1 vote
99 views

### Confusion regarding "epsilon" transition in NFAs, whether taking epsilon before or after reading the input affects the final states

Let's say we have a NFA as follows: It has 3 states, q1 - q2 - q3 and can make transition from q1 to q2 on 0 or epsilon and from q2 to q3 on 1 or epsilon My question is do we take epsilon transition ...
1 vote
93 views

53 views

### Why Regular Grammar is Left/Right Linear?

From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules) But, my question is why it is mandatory? Can't we ...
1 vote
49 views

### Check whether a regular expression is correct

I'm given a description of a regular language $L$, and I have a candidate regular expression $R$. Is there a systematic, step-by-step way to test whether the candidate regular expression is correct? ...
37 views

### What characteristics would a PDA $A$ where $L(A)=\Sigma^*$ have?

I understand that the problem of whether a PDA accepts all strings is undecidable. However that doesn't mean such PDAs exist. To start, I'm working under the assumption that a PDA must read it's ...
143 views

### If L = L1 U L2 is regular, L2 is the complement of L1 (which means L1 ∩ L2 = Ø), and we're given that L and L2 are regular, is L1 regular?

L1, L2, and L are not finite. We're given that L and L2 are regular. However, L1 ∩ L2 is empty, since L2 is the complement of L1. Is L1 regular under the property that regular languages are closed ...
23 views

### How are we sure choose is going to halt? question regarding a section from Elaine Rich's Automata, Computability and Complexity book?

I have a problem regarding the choose algorithm, I provide the algorithm's definition and it's use in the book,I attached a picture for the Illustration and for how the algorithm is used. choose (x ...
76 views

### Inverse operation to concatenation for regular languages

I'm currently in need of the inverse operation of the concatenation of 2 regular languages. Formally, for 3 regular languages $A,B,C$ such that $A \cdot B = C$, only $A$ and $C$ are known, and $B$ is ...
50 views

### Why must 2 distinct strings go to the same state in a DFA?

I'm finding it difficult to understand why due to the pigeonhole principle, 2 distinct words must go to the same state in a DFA. Is it that if there are n words and m states, where there are more ...
18 views

### complement of {a^lb^mc^n:n>l+m}

If we have this language $L = \{a^mb^nc^n:m,n \in N\}$, would its complement be $\{a,b,c\}^* \setminus L = L^\complement = \{c^nb^na^m:m,n \in N\}$? This was the professor's answer, which I find ...
91 views

### Regular language under intersection and complement confusion

I know that regular languages are closed under closure properties. But, for example, we know if $L$ is regular, then its complement $L^\complement$ is also regular. If we have $L_1$ and $L_2$ as ...
61 views

### Exists and forall in formal language definition in the case of kleene star [closed]

Let's suppose we have language $Y = \{a^ib^j:i,j \in N^*\}$ defined over the alphabet $\Sigma^{}_{} = \{a, b\}$ If we want to define this language $\Sigma^{*}_{}$ \ $\ Y$ such that we don't have the ...
62 views

### How to find the intersection of two FAs and then check if two FAs are equal?

I am still quite confused on how to properly handle in answering the intersection and equality of two FAs in terms of table form and manipulating its transformation....
28 views

### Finite Automata Mixture Combinatorics

Hello Folks, I am facing hard time in understanding this, basic question which says, how many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with ...
406 views

### DFA and NFA Equivalence Proof

I'm taking a Theory of Computation class and we went over the proof to show that for any NFA there is an equivalent DFA, which I understand the proof fully in this case. But if it were in reverse, for ...
34 views

### Models of computation less powerful than DFA

I wonder if there are "standard" models of computation that are less powerful than DFA that are still "mathematically interesting"? It is evident that restricting the set of DFAs ...
1 vote
27 views

### Compressed string lookup by name or ordinal

I have a large list of strings with associated values. I need to do a fast lookup into the list by the string prefix, but also by the string's ordinal within the list. For example, ...
101 views

### How to convert the regular expression $\emptyset^*$ to an NFA?

The question is to convert the following regular expression to an NFA: $\emptyset^*$. I know that the symbol phi in Theory Of Computation means an empty set. But what does phi^* mean?
71 views

### Is my DFA optimal?

I designed this FSM graph to demonstrate a DFA that would accept any string that is of length 5, must contain a d, can only have as and/or bs before the d, and can only have bs and/or cs after the d. ...
1 vote
73 views

### Does this DFA prove closure under Perfect Shuffle?

I'm self studying Introduction to Theory of computation and I'm a bit confused about a problem definition. I'm trying to understand and verify whether my proof is correct or not. Question: Prove that ...
1 vote
118 views

### does finite automata have memory?

I've learned that finite automata doesn't have memory and hence languages, where there are comparison within the string, can't be considered regular. In our university there was a question where the ...
29 views

### Is there some way to make JFLAP display the 5-tuple for the current DFA?

I am using JFLAP in my class and would like to produce the 5-tuple M={Q,Sigma, delta, q0, F} from the DFA I just created. Drawing a DFA from the 5-tuple would also be nice.
72 views

### minimal DFA transition function clearification

Statement: Given any dfa $M$, application of the procedure 'reduce' (see below) yields another dfa $\hat{M}$ such that $M$ and $\hat{M}$ are equivalent. Furthermore $\hat{M}$ is minimal in the sense ...
90 views

1 vote
60 views

### Optimal way to construct union automata of two DFAs

Given two DFAs, is it also a correct method to start with the combination of the initial states of both automata, then check where I can go for each symbol from these two states. Then add the ...
144 views

### Hopcroft's minimization algorithm produces an incorrect result for a particular regular expression

I'm writing a DFA minimizer using Hopcroft's algorithm. While testing some regular expressions, I came out with an issue in the algorithm's output relative to two particular regular expressions: a(b|...
71 views

### Show that if a DFA accepts all words of length < 2n then it accepts any word

Is it true that if a given DFA $M = \langle Q, \Sigma, \delta, q_0, F\rangle$ with $|Q| = n$ accepts all strings $w \in \Sigma^*$ such that $|w|\leq 2n$ then it accepts any $w \in \Sigma^*$ ?
44 views

### Transition System vs State Machines

Why there is no final state for a transition system? And why do NFA and DFA have final states? The transition system may or may not have any terminal states, but NFA/DFA has at least one final state (...
1 vote
108 views

### Comparing automata sizes given Myhill-Nerode equivalence under a function

Consider two finite languages, $L_A$ over alphabet $A$ and $L_B$ over alphabet $B$. $A$ might be the same as $B$. Since $L_A$ and $L_B$ are finite languages, there exist minimal acyclic deterministic ...
2k views

55 views

### How this state set of DFA was retrieved from the given NFA

I have this NFA: 1,{2, 3} 2,empty 3,{4} 4,empty All the arrows in this NFA are epsilon-arrows. I understand that all possible states that can be reached from each ...
43 views

### Confused by Sipser's proof of equivalence of R and NFAs

I am reading Introduction To Theory of Computation by Sipser, 3rd Edition and am confused by his take on the last three cases of proving that "if a language is described by regular expression ...
1 vote
54 views

### What complexity class is this?

Disclaimer 1: I am a beginner in this domain and I am self-learning these concepts. Please take this in consideration when reading my question. Disclaimer 2: All corrections to this question are ...
31 views

### Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular (without using complement closure)

Question: Use the Pumping Lemma to show $L_1 = \Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular, for $\Sigma=\{0,1\}$ (without using the complement closure property). My thoughts: I understand ...
### Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular
Question: Use the Pumping Lemma to show $L_1 = \Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular, for $\Sigma=\{0,1\}$. My thoughts: I understand that $L_2 = \{0^n1^n: n\geq 0\}$ can be shown to be ...