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,134
questions
0
votes
0answers
21 views
How to prove this language is not regular?
I am currently learning Pumping Lemma and found this question. But I am not able to prove it not regular. L = { $0^n$ | n is power of 2}. So, here I considered w = $0^{2^n}$ where n is constant of ...
1
vote
1answer
37 views
Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states
So, I came up with a DFA for the regular expression. Now for every string described by the regular expression, the DFA accepts it. But in order to ascertain if it's really a DFA for the regex, you ...
-1
votes
0answers
16 views
Construct an NFA over {0,1}* such that every string contain exactly two occurrence of 10
NFA is always a bit tricky than DFA atleast in the case of mine. Anyways, this problem seems easy but I just can't figure it out. I've tried it but the solution doesn't seem right.
0
votes
0answers
19 views
How to write ^ (to the power) in regex in PFLAP [on hold]
I am trying to convert this regex to NFA
(3^+)(3*+2*)(1^+)(2+1)*3*(2^+ )(3+1)*(3+1)*2*
but it says "Operators are poorly formatted!"
So, the question is: does ...
0
votes
1answer
23 views
Can you determinize an NFA in PSPACE?
QUESTION
Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$?
MORE DETAILS
I'm asking this as I want to be able to ...
0
votes
0answers
21 views
Meaning of cartesian product of DFA? [closed]
Cartesian product of two DFA (m1 X m2) will give the intersection/union/complement of the language accepted by m1 and m2 according to what state we set as final state.
Am i correct ?
I want to know ...
2
votes
2answers
76 views
Proof: There exists an irregular language L such that LLLL is regular
As title.
I consider finding a specific L to fulfill the condition stated to prove the statement, however, I have no luck in finding one.
A senior gave me a hint that Lagrange's four square theorem ...
0
votes
0answers
26 views
Converting DFA to RE [duplicate]
I have been trying to solve this problem.
Convert the DFA to a regular expression.
I extracted these following equation.
$q_1 = q_2a$
$q_2 = q_1a + (a+b)q_3$
$q_3 = q_1b + q_2a $
Also,the ...
0
votes
0answers
34 views
Testing if a state is in final state
Please excuse my language, I am new to the topic.
I am trying to classify/find a class of game that describes games such as chess, tic-tac-toe as a finite state machine.
For those games, final ...
0
votes
0answers
30 views
Fastest algorithm that determines whether a given DFA is minimal? [duplicate]
NOTE - I can't find a good answer in the Similar question above ^
Given a DFA, is there a fast algorithm that determines whether it's minimal?
I'm looking for an algorithm that works faster than ...
0
votes
1answer
38 views
Number of final states in minimal DFA for $a^*b^*+b^*a^*$ [closed]
How many final states exist in the minimal DFA that accepts the language $a^*b^* + b^*a^*$?
2
votes
2answers
560 views
Why can't DFA's have 0 exiting arrows for some input symbols?
Suppose you are in a middle of computation on a non accepting state and at this point, an input of 0 is rejected by the DFA. But, according to Sipser's formal definition, you must still draw an ...
0
votes
0answers
25 views
why does the pumping lemma want us to only consider the first repitition of states?
In Sipser's Intro to Theory and computation, He writes:
I don't understand the constraint on x. Shouldn't it be just y <=p? (Equal bc in the case when machine M runs through all states p) Making ...
2
votes
2answers
30 views
Given an non-deterministic finite automaton, will its determinization always have unreachable states?
Given an NFA that accepts the regular language L, will its equivalent DFA which accepts the same language L always have unreachable states.
If it does, why?
1
vote
1answer
55 views
what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata
my doubt is
what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata ?
both of them when started at a state q for a string w will ...
5
votes
4answers
2k views
Are Finite Automata Turing Complete?
Something is Turing Complete if it can be used to simulate any Turing Machine.
So, can a Finite Automaton simulate a Turing Machine?
On the question Can regular languages be Turing complete? they ...
2
votes
0answers
75 views
Intersection of two deterministic parity automata
Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
1
vote
1answer
24 views
A deterministic FA for $0^*1^*$ is required
A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required.
Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$,
both are ...
2
votes
2answers
45 views
Is the language L = {(a,b)* | #a * #b is an odd number} regular?
Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of $a$'s and the number of $b$'s is an odd number}\} $$
If i'm not mistaken the condition is the same as ...
2
votes
1answer
20 views
Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?
The canonical NFA to DFA conversion, starting with an NFA with $n$ states, can result in a DFA with $2^n$ states. However, in many cases, there are states that are "unnecessary," such as when ...
2
votes
1answer
44 views
Construct a DFA from the regular expression (a)*+(aab)*
I've broken down the expression into two simpler DFAs but right now I'm stuck.
I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.
2
votes
1answer
19 views
Proving a language comprised of 2 languages is regular(with suffix and prefix)
I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular:
$$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\...
4
votes
1answer
24 views
Proving a language comprised of 2 languages is regular
So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it.
The question:
$L_1$ and $L_2$ are regular languages over the ...
1
vote
0answers
25 views
Tree languages regular
Let $T_1,T_2 \subseteq T_\Sigma$ be regular tree languages, f a symbol with arity 2.
To proof: $\{f(t_1,t_2) \mid t_1 \in T_1, t_2 \in T_2\} \subseteq T_{\Sigma \cup \{f\} }$ is regular.
So it's ...
1
vote
1answer
52 views
Construction of a Deterministic Tree Automaton (DTA)
Let $L \subseteq \Sigma^*$ be a regular language. Let $\Sigma' = \Sigma_0 \cup \Sigma_2$ where $\Sigma_0 =\Sigma$ and $\Sigma_2=\{*\}$.
We define $T_L=\{t \in t_{\Sigma'} \mid \text{The leafs from t ...
2
votes
1answer
88 views
Finding a regular expression of a language
Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3.
Obviously $(aaa)^*(bbb)^*$ is one of the options, ...
1
vote
0answers
60 views
What is the word “madness” doing in the first chapter's title of Automata Theory, Languages and Computation by Hopcroft, Motwani, Ullman?
The chapter's title is "Automata: The Methods and the Madness". This title came along in the second edition and remains in the third edition. In the first edition, the the second chapter's title is "...
1
vote
1answer
32 views
In which reference can I find a definition for the equivalence of DFAs?
How is the equivalence of DFA defined? I found the equivalence of states --- James Hein, section 5.3, page 301. But he doesn't define equivalence between entire automata. (Ullman and Hopcropft seem ...
0
votes
0answers
26 views
Using Nerode theorem to prove that the following languages are non-regular
I've been trying to understand the idea behind proving a language is not regular by using Nerode's theorem, but I just couldn't apply the idea on what I've been asked.
The problem is to prove the ...
1
vote
1answer
36 views
Efficiently deciding whether TM accepts all inputs in at most $k$ steps
I want to decide if a deterministic TM $A=(Q, \varGamma, \delta, q_s, q_h)$ halts on every input in at most $k$ steps. If the TM $A$ stops after $k$ steps, then the positions $A$ can reach are ...
1
vote
3answers
70 views
DFA for a language that accepts the addition of multiple of 2 and multiple of 5
I am trying to draw a DFA that accepts the following language:
$L=\{a^{2i+5j} : i , j \geq 0\}$
I started out by drawing an NFA, which I can then convert to a DFA but I am not sure if my NFA is ...
1
vote
1answer
74 views
NFA that accepts all numbers not divisible by 105
I have to create an NFA that accepts the following language L with no more than 15 states.
$L = \{a^n \mid n \geq 1$ and $n \mod105 \neq 0 \}$.
To me it seems that all multiples of 105 have the ...
0
votes
1answer
39 views
Recognizing Regular Languages in Layman terms [duplicate]
I understand that regular languages are languages which can be computed by Finite Automata however i am having some trouble understanding how one can identify a regular from non-regular.
I know that ...
9
votes
1answer
1k views
Non-deterministic Finite Automata | Sipser Example 1.16
I am working through the Sipser Book (2nd edition) and came across this example, which I do not understand. In the book it states that this NFA accepts the empty string, $\epsilon$.
Could someone run ...
0
votes
1answer
48 views
Dana Angluin's L* algorithm - Hypothesis inconsistent
is it possible for the Dana Angluin's L* algorithm that a hypothesis is inconsistent?
So assume we have a closded observation table for a regular language L. Now after creating the hypothesis we will ...
1
vote
1answer
57 views
DFA multiple accepting states to Regular expression
I am trying to find the regular expression that defines this DFA, I am finding this particular case difficult since it has multiple accepting states.
If I understand this DFA correctly, it recognises:...
0
votes
2answers
69 views
Prove that the following language is regular [duplicate]
Let L1, L2 be regular languages. And let A1=〈Σ,Q,q0,𝛿1,F1), A2=〈Σ,P,p0,𝛿2,F2) be their DFA.
Prove that the following language is regular, by making an appropriate NFA for it:
𝐿3={𝜎1𝜎1′𝜎2𝜎2′…𝜎...
3
votes
1answer
51 views
ε-NFA to DFA - initial state with only epsilon transitions
I am having trouble discovering how to convert a ε-NFA to DFA (image below) when all transitions in the initial state are epsilon transitions. I already know how to convert ε-NFA to DFA (common cases),...
1
vote
0answers
28 views
Computational power of quantum finite automata
I am preparing some lecture notes on the computational power of quantum finite automata (QFA). I am a bit confused about which models of QFA are stronger and which models are weaker than standard ...
2
votes
2answers
56 views
Pumping lemma occurrence of c > d
I'm trying to prove a language is not regular through using pumping lemma, but can't seem to come up with any way of doing it.
The alphabet is:
$$ \Sigma = \{c, d\} $$
The language is:
$$ A = \{z ...
2
votes
1answer
43 views
The order of ε-transitions in NFA
I'm reading 'Introduction to the Theory of Computation' by Michael Sipser. He gives an example of a NFA, stating that this particular automaton accepts $a$ (he lists other strings as well, I just want ...
2
votes
1answer
50 views
Help with question from Sipser chapter 1
Is this language regular?
$0^k10^k \ with \ k\geq1$
It needs to count the starting and ending zeros which is impossible with finite states.
Update:
This is the whole problem from the book:
Let $\...
3
votes
0answers
39 views
Tree Automata Operators
I am trying to understand the Projection operation (linear tree homomorphism) and Cylindrification operation (inverse tree homomorphism) from the book. Linear Tree homomorphism is defined as follows:
...
0
votes
1answer
27 views
How to show a language is regular through creating DFA
I'm trying to prove that a given language is regular through proving that a DFA can be created from it, but have problems with how to the DFA should look.
The alphabet is $\Sigma=\{0, 1\}$ and the ...
-1
votes
1answer
124 views
Backtracking in DFA [closed]
Is it true that backtracking is allowed in deterministic finite automaton (as mentioned in many comparisons between DFA and NDFA)? If yes, how is it possible when transition in DFA is to a single ...
0
votes
1answer
104 views
Limitations of DFA [duplicate]
In this link it is mentioned:
A DFA is not powerful enough to recognize many context-free languages because a DFA can't count.
But counting is not enough -- consider a language of ...
1
vote
1answer
39 views
Simple property of DFAs
Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)?
Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, ...
1
vote
1answer
39 views
How to check if DFA is actually a correct model of the intended system?
Suppose I have modeled a deterministic finite automaton of my system. How can I check if the traces generated by this system, actually represent the model I had in mind?
For example, say I have DFA ...
1
vote
1answer
49 views
Why are those very similar languages in a different complexity class?
i am having a real time understand why the following two languages are in two different complexity classes(the first is NP-Hard and the second is in P). tried to look online at various resources and ...
0
votes
3answers
88 views
Define a finite automaton accepting the language below [duplicate]
$\{ w∈(a,b)^\ast | w $ does not contain '$ab$' as a subword $\}$.
About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite ...
