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.

Filter by
Sorted by
Tagged with
137 votes
4 answers
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 ...
Raphael's user avatar
  • 71.8k
39 votes
5 answers
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 ...
Julio Garcia's user avatar
37 votes
8 answers
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 ...
parvin's user avatar
  • 609
36 votes
2 answers
2k views

Planar regular languages

In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\...
Hendrik Jan's user avatar
  • 29.1k
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
31 votes
4 answers
100k 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
  • 313
31 votes
4 answers
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 ...
Aadit M Shah's user avatar
26 votes
3 answers
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 ...
Daniil's user avatar
  • 2,157
24 votes
7 answers
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., ...
Alex S's user avatar
  • 257
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
22 votes
4 answers
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 ?
gpuguy's user avatar
  • 1,769
20 votes
1 answer
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 ...
sanjeev mk's 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
19 votes
3 answers
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 ...
Daniil's user avatar
  • 2,157
19 votes
1 answer
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 ...
Yuval Filmus's user avatar
18 votes
2 answers
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.
Chris's user avatar
  • 181
18 votes
2 answers
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 ...
Madhuri's user avatar
  • 189
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
17 votes
3 answers
7k 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
16 votes
4 answers
9k views

Why is NFA minimization a hard problem when DFA minimization is not?

I know that we can minimize DFAs by finding and merging equivalent states, but why can't we do the same with NFAs? I'm not looking for a proof or anything like that--unless a proof is simpler to ...
Duncan's user avatar
  • 665
16 votes
2 answers
570 views

Languages accepted by modified versions of finite automata

A deterministic finite automaton (DFA) is a state machine model capable of accepting all and only regular languages. DFAs can be (and usually are) defined in such a way that each state must provide ...
Patrick87's user avatar
  • 12.7k
15 votes
7 answers
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 ...
Madhusoodan P's user avatar
15 votes
5 answers
40k 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
15 votes
7 answers
13k views

Can we say DFA is more efficient than NFA?

I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it ...
avi's user avatar
  • 1,453
15 votes
3 answers
39k 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
1 answer
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 ...
Chill's user avatar
  • 305
15 votes
1 answer
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$. ...
john_leo's user avatar
  • 1,861
14 votes
2 answers
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 ...
yoyo_fun's user avatar
  • 818
14 votes
3 answers
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 ...
user avatar
14 votes
1 answer
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 ...
Walter Schulze's user avatar
13 votes
3 answers
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 ...
HQuser's user avatar
  • 245
13 votes
4 answers
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. ...
Keio203's user avatar
  • 257
13 votes
2 answers
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 ...
jmite's user avatar
  • 29.5k
13 votes
1 answer
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 ...
Jesse Berlin's user avatar
12 votes
4 answers
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 ...
mrk's user avatar
  • 3,650
12 votes
2 answers
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? ...
Richard Jones's user avatar
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
3 answers
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 ...
zell's user avatar
  • 374
11 votes
2 answers
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 ...
Ben I.'s user avatar
  • 1,652
11 votes
2 answers
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 ...
Issam Mani's user avatar
11 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
  • 152k
11 votes
2 answers
690 views

Is the reversal of a minimal DFA also minimal?

The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with $...
jmite's user avatar
  • 29.5k
11 votes
3 answers
2k views

Algorithms for minimizing Moore automata

Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times ...
Ajeet Singh's user avatar
11 votes
1 answer
6k 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
  • 111
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
11 votes
1 answer
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 ...
Anurag Kalia's user avatar
10 votes
4 answers
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 ...
zic10's user avatar
  • 201
10 votes
4 answers
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 ...
Ser Pounce of House Whiskers's user avatar
10 votes
3 answers
3k 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
10 votes
1 answer
873 views

What is the correct way to draw NFA of RE (a|b|c)?

We were assigned to draw NFA for regular expression a|b|c, so like any one I draw this But my professor told me it is wrong, the correct way is So, I checked it ...
Harshil Modi's user avatar

1
2 3 4 5
35