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
201k views

### How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
51k views

### Difference between a turing machine and a finite state machine?

I am doing a presentation about Turing machines and I wanted to give some background on FSM's before introducing Turing Machines. Problem is, I really don't know what is VERY different from one ...
10k views

### Are there any non-finite automata?

In automata theory, we all read automata as finite automata, from the very beginning. What I want to know is, why are automata finite? To be clear, what is it in an automaton that is finite - the ...
2k views

6k views

### How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?

I created a simple regular expression lexer and parser to take a regular expression and generate its parse tree. Creating a non-deterministic finite state automaton from this parse tree is relatively ...
3k views

### What are the conditions for a NFA for its equivalent DFA to be maximal in size?

We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in ...
14k views

### Why is English not a regular language?

Surely any language with a finite longest word can be made regular by having an automaton with paths to 26 states for all letters and then having each of those states go to another 26 states, etc., ...
7k views

### How to prove that DFAs from NFAs can have exponential number of states?

All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. ...
38k views

### What is the difference between finite automata and finite state machines?

I have used FSM in Digital sequential Circuit designs. But I am unfamiliar with Finite Automata. Can somebody help me in understanding 'basic' difference between the two ?
34k views

### Intersection of context free with regular languages

The intersection of a context free language L with a regular language M, is said to be always context free. I understood the cross product construction proof, but I still don't get why it is context ...
17k views

### How do I write a proof using induction on the length of the input string?

In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however ...
443 views

### Is this language defined using twin primes regular?

Let $\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$ Is $L$ regular? This question looked suspicious at the first glance and I've realized that it is connected with the ...
692 views

### Exponential separation between NFAs and DFAs in the presence of unions

For a regular language $L$, its DFA complexity is the size of the minimal DFA accepting it, and its NFA complexity is the size of the minimal NFA accepting it. It is well-known that there is an ...
7k views

### Can a deterministic finite automaton ever go into an infinite loop?

As the title suggests, is this possible? Or does it halt execution when it hits the trap state? Thanks to anyone who can clear this up.
6k views

### Can a language have more than one DFA?

For Example when we consider a DFA that allows the strings having neither sub strings 00 or 11 I can produce the following two ...
3k views

### What are the possible sets of word lengths in a regular language?

Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$: $$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$ Which sets of integers can be the length set of a regular language?...
7k views

2k views

### Can a Turing Machine decide if an NFA accepts a string of prime length?

I want to know if the following problem is decidable: Instance: An NFA A with n states Question: Does there exist some prime number p such that A accepts some string of length p. My belief is that ...
940 views

### The number of different regular languages

Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state non-deterministic finite automaton? As an example, let us consider $n=3$. ...
3k views

### How did the word "production" end up being a synonym with the word "rule" in the context of Computer Science?

I am studying formal languages and production bases systems (rule-bases systems) and I am a little confused about why do these two word "production" and "rule" mean the same thing in so many context ...
24k views

### How to create DFA from regular expression without using NFA?

Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that? I asked this question to our professor but he ... 2k views

### Monadic Second Order Logic for Dummies

I am programmer with a grip on automata, but not on logic. I read in papers that the two are very tightly related. Deterministic Finite Automata (DFA), Tree Automata and Visibly Pushdown Automata are ...
4k views

### Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?

Tomorrow is my presentation and I want to clear my concepts… I've read that in DFA, "For each state, transition on all possible symbols (alphabet) should be defined." Is for each state, defining ...
3k views

### Proving Equivalence of Two Regular Expressions

Consider the regular expressions $(1+01)^*(0+\epsilon)$ $(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$, where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. ...
2k views

### What is the complexity of the emptiness problem for 2-way DFAs?

I'm wondering, what is the time-complexity of determining emptiness for 2-way DFAs? That is, finite automata which can move backwards on their read-only input tape. According to Wikipedia, they are ...
4k views

### What is the relationship between Turing Machines with a finite tape and Finite State Automata?

I seem to recall from an undergraduate class that for a Turing Machine with a finite tape there will always exist a corresponding Finite State Automata, but I've been unable to find this confirmed ...
6k views

### NFA with exponential number of states when determinized

How can I build an example of a regular language where the minimal DFA has $2^n$ states and the minimal NFA has $n$ states? Obviously the DFA's state-set should contain all subsets of the the NFA's ...
6k views

### Is the equality of two DFAs a decidable problem?

So given two DFAs, is the problem of finding if they generate the same language a Decidable problem? I already know that Equality of two CFL is not Decidable but what about Equality of two DFAs? ...
4k views

### Can an FSA count?

This may be a silly question. It seem clear that an FSA, since it is finite, can only count the number of symbols in its input string up to a number bounded by the number of its states. But now ...
1k views

### How to convert an NFA with overlapping cycles into a regular expression?

If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as ...
3k views

### Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?

I was under the impression that our computers, being finite, are ultimately no more powerful than (extraordinarily large) Finite State Machines. However, Linearly Bounded Turing Machines are also ...
5k views

### Can a DFA have an unreachable state?

I am trying to prove or disprove the following statement: If $A = (\Sigma, Q, \delta, q_0, F)$ is a complete DFA where $F \neq \emptyset$ then $L(A) \neq \emptyset$ So my initial thinking is to ...
2k views

### Smallest DFA that accepts given strings and rejects other given strings

Given two sets $A,B$ of strings over alphabet $\Sigma$, can we compute the smallest deterministic finite-state automaton (DFA) $M$ such that $A \subseteq L(M)$ and $L(M) \subseteq \Sigma^*\setminus B$?...
690 views

2k views

### Not able to convert from NFA to DFA

I have a simple problem of making a DFA which accepts all inputs starting with double letters (aa, bb) or ending with double letters (aa, bb), given $\Sigma =\{a, b\}$ is the alphabet set of the given ...
3k views

### Regular language not accepted by DFA having at most three states

Describe a regular language that cannot be accepted by any DFA that has only three states. I'm not really sure where to start on this and was wondering if someone could give me some tips or advice. I ...
2k views

### Words that have the same right- and left-associative product

I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting: Give a non deterministic finite automaton accepting ...
### If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I'm am stuck solving the next exercise: Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\}$ (i.e. the right quotient) is context-...