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