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.

Filter by
Sorted by
Tagged with
140 votes
4 answers
205k 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 ...
Raphael's user avatar
  • 72.3k
12 votes
4 answers
7k 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 ...
mrk's user avatar
  • 3,688
17 votes
3 answers
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?...
Gilles 'SO- stop being evil''s user avatar
14 votes
3 answers
25k 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 ...
user avatar
32 votes
4 answers
7k 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 ...
Aadit M Shah's user avatar
15 votes
5 answers
42k 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?
Duncan's user avatar
  • 665
10 votes
3 answers
4k 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-...
Dommicentl's user avatar
2 votes
2 answers
10k views

Convert regular expression to DFA

How do you construct a DFA from a language that has a + sign? e.g. $L = \{(a+b)\}*$
user avatar
20 votes
1 answer
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 ...
tcdowney's user avatar
  • 303
20 votes
1 answer
36k 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 ...
sanjeev mk's user avatar
9 votes
1 answer
10k views

Prove that regular languages are closed under the cycle operator

I've got in a few days an exam and have problems to solve this task. Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation $\operatorname{cycle}(L) = \{ xy \mid x,y\in \...
user1594's user avatar
  • 541
5 votes
3 answers
6k views

Is {wxw^r} a regular language?

Is $\{ WxW^{\mathrm{R}} \mid W,x\in\{0,1\}^+\}$ a regular language? If so, why? The notation $W^{\mathrm{R}}$ means the reverse string of $W$? If we consider the best answer in this solution, ...
Somenath Sinha's user avatar
33 votes
4 answers
106k views

How to show that a "reversed" regular language is regular

I'm stuck on the following question: "Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{...
Cat's user avatar
  • 333
12 votes
4 answers
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 ...
Torbjörn's user avatar
  • 131
12 votes
1 answer
7k 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 ...
user99163's user avatar
  • 121
23 votes
3 answers
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. ...
John Hoffman's user avatar
12 votes
2 answers
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$?...
D.W.'s user avatar
  • 158k
9 votes
2 answers
16k 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 ...
James Pekon's user avatar
7 votes
2 answers
34k 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 ...
Unni's user avatar
  • 71
7 votes
1 answer
6k 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 ...
Jules's user avatar
  • 337
5 votes
5 answers
62k 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)...
Iancovici's user avatar
  • 665
7 votes
1 answer
2k views

Removing $\epsilon$ transitions in a NPDA

NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions. However, NFA's with $\epsilon$ transitions could be converted to those without any $\...
0xffffffff's user avatar
5 votes
4 answers
12k views

Decide whether a DFA accepts the empty language

Let $X = \{\langle M \rangle\ |\ M\text{ is a finite state machine and }L(M) = \emptyset\}$ where $\langle M \rangle$ is an encoding of the machine $M$. Is $X$ Turing decidable? Why or why not?
Joe's user avatar
  • 61
2 votes
1 answer
11k views

Product construction for given two finite automata

I need to construct a finite automata which accept a language $L = L_1 \cap L_2$, where $L_1$ and $L_2$ are given below. $L_1 = \{ w \mid w $ is divisible by 2 } $L_1 = \{ w \mid w $ is ...
user7511700's user avatar
1 vote
1 answer
377 views

Myhill–Nerode equivalence classes of $\{0^n1^n \mid n \in \mathbb{N}\}$

I am told to find the equivalence classes of the Myhill–Nerode relation of the language $\{0^n1^n \mid n \in \mathbb{N}\}$. For one, I know it has an infinite number of equivalence classes given that ...
MR.CODER1111's user avatar
11 votes
5 answers
25k 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?
Davis8988's user avatar
  • 213
7 votes
3 answers
10k 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 ...
user avatar
6 votes
4 answers
20k 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 ...
asheeshr's user avatar
  • 221
5 votes
3 answers
15k views

Regular expression for strings that begin with 0 and contain an equal number of 01 and 10 substrings

I'm trying to write a regular expression for the language $L\subseteq\{0,1\}^*$ of strings that begin with $0$ and contain an equal number of occurrences of the substrings $01$ and $10$. ...
Lurr's user avatar
  • 147
5 votes
1 answer
5k 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 ...
Mr. Sigma.'s user avatar
  • 1,293
5 votes
1 answer
3k views

Prove that the language of non-prime numbers written in unary is not regular

Im trying to prove that the following language is not regular. $$\text{Notprime} = \{a^n \text{where \(n\) isn't prime}\} = \{\epsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots\}$$ Heres what I have: "If ...
user avatar
3 votes
3 answers
5k views

Proof that whether a regular language is finite is decidable [duplicate]

I have this question for a homework. The question stems from the fact that you can determine whether a regular language is empty by using a Turing machine to count the states n in the given FSM. When ...
Bronze's user avatar
  • 51
3 votes
1 answer
2k 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 ...
PlsWork's user avatar
  • 427
1 vote
1 answer
360 views

Zigzag concatenation of two languages

Given two regular languages $A,B$ on the same alphabet $\Sigma$, I want to show that the following language is regular: $$ \{a_1b_1 \ldots a_kb_k \in \Sigma^* \mid a_1,\ldots,a_k,b_1,\ldots,b_k \in \...
WindBreeze's user avatar
1 vote
1 answer
205 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? ...
D.W.'s user avatar
  • 158k
0 votes
1 answer
1k views

Proving following regular expressions equal to one another?

How would I go about proving the following two regular expressions are equal to one another: ( a + b )* a ( a + b )* b( a + b )* = (a + b)* ab(a + b)* I can "see"...
Jenna Maiz's user avatar
0 votes
1 answer
3k views

How to construct a DFA for this?

Let $C = shuffle(A, B)$ denote the shuffle $C$ of two languages $A$ and $B$, it consists of all strings $w$ of the form $w = a_1b_1a_2b_2....a_kb_k$, for $k > 0$, with $a_1a_2 ··· a_k \in A$ and $...
James Yang's user avatar
0 votes
2 answers
4k views

Are supersets of non-regular languages also non-regular?

I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid? Since $L_1$ is not regular, there does not exists a finite automata $M_1$ ...
Kevin's user avatar
  • 129
32 votes
2 answers
3k views

Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
Phil Wright's user avatar
23 votes
4 answers
40k 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 ?
gpuguy's user avatar
  • 1,799
17 votes
3 answers
8k views

Brzozowski's algorithm for DFA minimization

Brzozowski's DFA minimization algorithm builds a minimal DFA for DFA $G$ by: reversing all the edges in $G$, making the initial state an accept state, and the accept states initial, to get an NFA $N&#...
Artem Kaznatcheev's user avatar
15 votes
3 answers
42k views

How does an NFA use epsilon transitions?

In the picture below, I'm trying to figure out what exactly this NFA is accepting. What's confusing me is the $\epsilon$ jump at $q_0$. If a $0$ is entered, does the system move to both $q_0$ and $...
user3472798's user avatar
15 votes
7 answers
7k 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 ...
Madhusoodan P's user avatar
12 votes
2 answers
7k 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? ...
Richard Jones's user avatar
11 votes
1 answer
1k views

How fast can we decide whether a given DFA is minimal?

Minimizing deterministic finite automata (DFAs) is a problem that has been thoroughly studied in the literature, and several algorithms have been proposed to solve the following problem: Given a DFA $...
Cornelius Brand's user avatar
10 votes
1 answer
2k views

Is there a way to test if two NFAs accept the same language?

Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA. If I do a search through every path of the NFA, will that work? Although that will take a long time.
Duncan's user avatar
  • 665
10 votes
2 answers
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 ...
R B's user avatar
  • 2,634
10 votes
3 answers
3k views

How do I verify that a DFA is equivalent to a NFA?

I'm learning how to convert NFAs to DFAs and I want to make sure I'm doing it right. Obviously, going back in the other direction isn't a thing. Does anyone know of an algorithm to check that a DFA is ...
IAmOnStackExchange's user avatar
9 votes
1 answer
603 views

Problem with implementing Brzozowski's algorithm

I've been trying to implement Brzozowski's algorithm but I've just discovered that it creates suboptimal automata for a certain class of inputs, having one more state than what is really needed in the ...
Přemysl J.'s user avatar
9 votes
4 answers
1k views

What is a good algorithm for generating random DFAs?

I am generating random DFAs to test a DFA reduction algorithm on them. The algorithm that I'm using right now is as follows: for each state $q$, for each symbol in the alphabet $c$, add $\delta (q, c)...
Duncan's user avatar
  • 665

1
2 3 4 5