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

165 questions
Filter by
Sorted by
Tagged with
178k 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 ...
2k 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?...
5k views

### NFA with exponential number of states when deteminized

How can I build an example of a DFA that has $2^n$ states where the equivalent NFA has $n$ states. Obviously the DFA's state-set should contain all subsets of the the NFA's state-set, but I don't know ...
23k 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 ...
27k views

### In a DFA, does every state have a transition on every symbol of the alphabet?

If not, then what does it mean when for some state $q$ and some symbol $a$, $\delta(q, a)$ does not exist?
9k views

### Convert regular expression to DFA

How do you construct a DFA from a language that has a + sign? e.g. $L = \{(a+b)\}*$
5k 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 ...
15k 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 ...
2k views

### 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-...
26k 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 ...
7k views

24k views

### Complement of Non deterministic Finite Automata

It's known that the complement of a DFA can be easily formed. That is, given a machine $M$, we can construct $M'$ such that $L(M') = \Sigma^* \setminus L(M)$. Is it possible to construct such a ...
52k views

### Regular expression for the strings without a particular substring

How can we design a regular expressions without particular substrings. The goal of this is to create language L which won't contain a particular substring (i.e. 110)...
5k 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. ...
5k views

### If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$

I am interested in proving that $\sqrt{L}=\{w:ww\in L\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right ...
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$?...
4k views

### DFA for a strings whose every subsequence of length five has at least two zeroes

I have a regular language consisting of such {0,1}^k sequences, in which every subsequence of length 5 has at least two 0's in ...
5k views

### Why is every finite language A ⊆ Σ* regular

So I've been doing regular languages a while and still need a better understanding of why all finite languages A ⊆ Σ* are regular? Is there a formal proof of it or is it just because a DFA can ...
3k views

### Minimum number of states in the DFA

I am trying to solve following problem but unable to solve this. Can anyone tell me how to approach this kind of problems where it is not easy to make DFA. The minimum number of states required to ...
17k views

### Designing a DFA that accepts strings such that nth character from last satisfies condition

This is a homework question, so I am only looking for hints. I got a question in an assignment which states : Design a DFA that accepts strings having 1 as the 4th character from the end, on the ...
9k views

### I need clarification about DFA's and DFA acceptable languages

In class yesterday we went over DFA's and DFA acceptable languages. An example of a language that is not DFA acceptable was given as $\{ ab, aabb, aaabbb, aaaabbbb, \ldots \}$. The reason given was ...
983 views

6k views

### Why NFA is called Non-deterministic?

I have this [kind of funny] question in mind. Why is the non-deterministic finite automaton called non-deterministic while we define the transitions for inputs. Well, even though there are multiple ...
11k views

### Practical application of Finite State Machines

I am looking for practical applications of Finite State Machines like DFA, NFA, Moore, Mealy machines... It would be helpful if someone point to examples from Linux Kernel. I know that DFA is used in ...
13k views

### How to determine if an automata (DFA) accepts an infinite or finite language?

Given an automata [DFA $A=(Q,Σ,δ,q_0,F)$], is there a way to determine whether it accepts an infinite or finite language?
2k views

### Proving regular languages are closed under a form of interleaving

I've got the following definitions: $$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$ when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means ...
986 views

1k views

### Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
3k views

### Automaton for substring matching

Given $s$ as a string over some alphabet, what is the best known algorithm to compute a corresponding deterministic finite-state automaton (DFA) that accepts any string that contains $s$? I am mostly ...
1k views

### Right moving turing machines and FSA's

I stumbled upon the following post while learning about turing machines: Right moving turing machine I kind of understand the intuition behind why a TM that only moves to the right works like a FSA ...
770 views

### Runtime of the binary-GCD state machine

I am doing self study from MIT OCW exercises and I could not understand this question. The following rules define the binary-GCD state machine working on states in $\mathbb{N}^3$ with start state \$(...