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.
207
questions
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 ...
- 71.8k
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 ...
- 3,650
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?...
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 ...
user4220128
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 ...
- 435
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?
- 665
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-...
- 201
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)\}*$
messivp
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 ...
- 303
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 ...
- 399
8
votes
1
answer
9k
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 \...
- 511
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, ...
- 335
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^{...
- 313
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 ...
- 131
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 ...
- 111
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. ...
- 397
9
votes
2
answers
13k
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 ...
- 131
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 ...
- 337
7
votes
2
answers
33k
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 ...
- 71
5
votes
5
answers
61k
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)...
- 665
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.♦
- 152k
7
votes
1
answer
1k
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 $\...
- 93
5
votes
4
answers
11k
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?
- 61
1
vote
1
answer
242
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 ...
- 41
10
votes
5
answers
23k
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?
- 103
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 ...
user16480
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 ...
user3115
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 ...
- 1,263
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$. ...
- 147
5
votes
4
answers
19k
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 ...
- 201
3
votes
3
answers
4k
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 ...
- 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 ...
- 427
1
vote
1
answer
9k
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 ...
- 39
1
vote
1
answer
290
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 \...
- 251
1
vote
1
answer
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?
...
D.W.♦
- 152k
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"...
- 255
0
votes
2
answers
3k
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$ ...
- 129
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 $...
- 123
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 ...
- 883
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 ?
- 1,769
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&#...
- 4,792
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 ...
- 290
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? ...
- 307
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 $...
- 1,281
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.
- 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 ...
- 2,624
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 ...
9
votes
1
answer
3k
views
Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?
Let a input string be given as $w_1w_2...w_n$. Then if a NFA is currently in state $r$ ( and has read the input upto alphabet $w_i$ ) then before reading the next input symbol the NFA splits into two ...
- 2,923
9
votes
1
answer
538
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 ...
- 193
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)...
- 665