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.

learn more… | top users | synonyms

1
vote
3answers
59 views

Are there any steps or rules to draw a DFA?

In my first lecture of "Theory of Automata", after giving some concepts of Alphabet, Language, transition function etc. and a couple of simple automata of an electric circuit with one and two ...
0
votes
0answers
20 views

A Java implementation of the Transitive closure method to generate a regular expression from a finite automata [closed]

I am working on a small application that collects some important operations about automatas. and there is my problem : I Can't find what's wrong with this implementation since 2 days ago : ----> ...
1
vote
2answers
115 views

Help me resolve my doubts about infinities, exemplified by an example of non DFA acceptable language

I have always had a hard time making sense of infinities. Example: the language $L = \{ \epsilon , 01, 0011, 000111, 00001111, ... \}$ is not DFA acceptable because a machine capable of ...
0
votes
0answers
46 views

Constructing nondeterministic pushdown automata

I having trouble constructing NPDAs for these two languages: $L_1 = \{a^nb^m \mid 2n \le m \le 3n\}$ $L_2 = \{a^nb^mc^k \mid n = m \: or \: m \ne k\}$ Would these be the proper states for the first ...
6
votes
3answers
194 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 ...
0
votes
2answers
33 views

NDFA associated with language L

Let A = $(Q, \Sigma, \delta, S, F)$ be a deterministic finite automaton associated with the language $L \subseteq \Sigma^*$ $L' = \{y \in \Sigma^*:\exists x\in L. |x| = |y|\}$ $L \subseteq ...
-1
votes
1answer
43 views

How to read edge labels like “01, 1” on a state diagram?

Is this state machine a moore machine or a mealy machine? I am confused because the states have outputs and the transitions have output based on the input. I tried making a state table but I think ...
2
votes
3answers
157 views

Does there exist a proof of closure of regular languages under regular substitution by giving the corresponding DFA?

Every proof I can find of this result is by way of regular expressions. Is there any "constructive" proof that defines the corresponding DFA (probably NFA)? For instance the proof of concatenation ...
1
vote
1answer
29 views

Proof that $A_{DFA}$ is decidable in Sipser

It seems like the proof that $A_{DFA}$ is decidable in Sipser (2nd ed.) assumes the computation will halt... and hence only really proves that $A_{DFA}$ is recognizable. The language $A_{DFA}$ is ...
4
votes
2answers
54 views

What is Finite Automata Bowl?

I was trying to find info about this Finite Automata type FAB (Finite Automata Bowl) and wasn't able to find a lot. It is basically the rules that apply to PDA apply to FAB except you drop the ...
3
votes
3answers
225 views

Do all states in a DFA must be connected?

Could I construct (for some wired reason) a DFA that has a state that is not connected to anything, and it would still be legal? I'm studying for a test, and I found a question that asks if an ...
2
votes
1answer
68 views

Are all DFAs also NFAs?

Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?
0
votes
0answers
44 views

how to convert Finite Automata into Push Down Automata

I am trying to convert Finite Automata into Push Down Automata and I am not sure if I am doing this right. There are not many good tutorials on this topic that I can find, but this is what I have. I ...
0
votes
1answer
36 views

What does an input string of epsilon mean?

I am currently reading Introduction to the Theory of Computation (Sipser), and after introducing epsilon labeled transition arrows, the book shows the following NFA: I was following it until I read ...
3
votes
1answer
66 views

Adding words to DFA, maintaining minimality

How can we add new words to DFA, maintaining minimality? Maybe, you can advise some completely different approach to solve the following problem: A program must process two types of queries: ...
9
votes
1answer
120 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 ...
0
votes
2answers
51 views

find a regular expression and FA that each define $L_1 \cap L_2$

I am trying to find a regular expression and finite automaton that each define $L_1 \cap L_2$, where $L_1 = (ab^*)^*$ and $L_2 = ...
2
votes
2answers
71 views

What languages does a (1-way) quantum finite state automata recognize?

Sorry if this is well known, but most of the research is paywalled. So far I know that it is a subset of the regular languages, but I cannot seem to find any (available) research which pins it down. ...
-1
votes
1answer
50 views

Given 2 regular languages and their DFA's, how to construct the DFA of the union?

Suppose $L1, L2$ are both regular languages and $A1, A2$ are their corresponding DFA's. How can I construct a new DFA for the regular language $L1 \cup L2$?
2
votes
1answer
56 views

What is the possible number of states in the DFA of intersection of two given FA?

Consider a DFA over $a,b$ accepting all strings having number of $a$ 's divible by 6 and number of $b$ 's divisble by 8. What is the minimum number of states in the resultant DFA ? This problem ...
2
votes
1answer
87 views

showing that the pair of Finite Automata are equivalent

Here I am trying to show that the pair of Finite Automata are equivalent. I have tried something but I am not sure if I am in the right direction. This is what I have. These are pairs of FA's. Set ...
10
votes
4answers
494 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 ...
3
votes
3answers
119 views

Minimum number of states in DFA for the given language?

While studying automata theory a typical problem that I face is of the following type: Constructing a DFA with minimum number of states for all strings over $\{a,b\}$ which have number of $a$’s ...
1
vote
1answer
56 views

Why the given NFA is not possible

I am trying to construct NFA for all languages ending in 00. I got this and this First one I could convert to DFA by subset construction and I got the correct DFA. For the second one I got the ...
4
votes
2answers
113 views

More than one NFA accepting a given language

While going through certain problems. it seems that more than one NFA is possible for the given language. Is it so? For example for drawing: NFA ending with 1 where $\Sigma=\{0,1\}$ is and also ...
0
votes
1answer
32 views

Non-Deterministic FSA to Deterministic FSA, Two initial states

My method of conversion is by creating a reachable set tree and each set within the tree would represent the new states. I have never dealt with FSAs that has 2 or more initial states. How do i ...
2
votes
2answers
52 views

Can a DFA have two symbols on one arrow?

I know that a DFA has to have exactly one transition for each symbol in the alphabet, but is it allowed to have two symbols on the same arrow? If, for example, I have a DFA with states $q_0$ and ...
1
vote
1answer
75 views

Can reversing the final and non-final states of a DFA produce the complement of the original language?

Is this true? If I change all final states of a given Deterministic Finite Automata to non final states and all non final states to final states then does this new automata represent the complement of ...
-1
votes
1answer
84 views

Why does this automation accept the empty string?

I am new to Automata Theory. I am studying the book thoroughly and understanding it well. I have got a confusion regarding NFA. Why does this automaton accept the empty string λ? What I think is ...
1
vote
2answers
56 views

2 threads accepted at the same time [closed]

Assuming we have an automaton that simultaneously accepts a string on two paths. Would this mean that the construction of the NFA might be faulty? In other words; at the end of any string over any ...
1
vote
2answers
61 views

Direct construction of NFA for the difference of regular languages

Let $A$ and $B$ be regular languages. Let $C$ be their difference, i.e $C = B \setminus A$. Given NFAs for $A$ and $B$, is it possible to directly construct an NFA for $C$ without (implicitly or ...
0
votes
0answers
30 views

Non-deterministic finite state automoton [duplicate]

I am taking a course in the theory of computation and am trying to understand how to correctly design NFA's so that I can transform them into regex. I was wondering if I have Sigma={a,b} and need to ...
0
votes
0answers
85 views

Non determininstic finite state automata [closed]

I wanted to construct a NFA over sigma star, where sigma={a,b}, such that at least one of the last 2 symbols is an "a". I just wanted to make sure that this construction is correct. Original image ...
3
votes
1answer
72 views

NFA to DFA final states proof

When translating an NFA into an equivalent DFA, we can say that all states that contain the final states of NFA, is the final state of DFA. What should my arguments be in order to prove this? ...
1
vote
1answer
40 views

Finite Automata Input Confusion

I am looking at the following non-deterministic finite automata which accepts all strings that end with at least 2 bs. I am wondering what would happen when you have the input string 'abba' with this ...
1
vote
2answers
104 views

DFA for exactly two of a and one or more of b

I'm totally new to DFA's and automaton in general -- this is the first week or two of class that I've actually seen this -- and I'm curious as to a pattern to match the following: "Match the set of ...
7
votes
2answers
151 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 ...
3
votes
0answers
90 views

C(++) library for DFAs - free for academic use

(I'm aware that software questions are better suited for stackoverflow, but since DFAs are not something that software developers usually care about, I hope it's alright if I ask here.) I'm currently ...
1
vote
1answer
95 views

iterating over subsets by switching one element at a time

How do I iterate over all the $k$-element subsets of $\{1,2,\dots, n\}$ by switching one element at a time? 123 134 234 124 145 245 345 135 235 125 This comes ...
4
votes
2answers
110 views

Decidability of $\lbrace \langle D \rangle \mid \text{$D$ accepts $a^kb^k$ for some $k > 0$}\rbrace$

I'm trying to understand decidable languages. In particular, I would like to show that $$B = \lbrace \langle D \rangle \mid \exists k \geq 0 \,.\,\text{DFA $D$ accepts $a^k b^k$}\rangle.$$ I don't ...
0
votes
1answer
22 views

Decidability. $\lbrace \langle D \rangle \mid \text{$D$ accepts $a^kb^k$ for some $k > 0$}\rbrace$ [duplicate]

I'm trying to understand decidable languages. In particular, I would like to show that $$B = \lbrace \langle D \rangle \mid \exists k \geq 0 \,.\,\text{DFA $D$ accepts $a^k b^k$}\rangle.$$ I don't ...
1
vote
1answer
103 views

how to solve NFA acceptance problem in polynomial time

I need to show that the language Anfa = {(A,w)| A is an nondeterministic finite automata that accepts w} can be decided in polynomial time. My problem is every solution that I think of requires ...
0
votes
1answer
214 views

How to approach NFA design questions intuitively? [closed]

I did see a lot of nice and informative questions, articles on inter-net and on StackOverflow itself, of-course. But I found all the questions or articles following a specific rule or a pattern to ...
1
vote
1answer
211 views

Redundant States During Removal of Null-Moves (Regular Expression to DFA)

I've had this little doubt bothering me since four semesters now, so I've come here to resolve it. Theoretical CS was probably not the right place to ask. Coming to the question, my old coursebook ...
3
votes
1answer
146 views

Synchronizing sequence and Synchronizable DFA

I am trying to prove problem 1.59 in Sipser's book: Introduction to the theory of computation , 2nd Edition. Let $M=(Q,\Sigma,\delta,q_0,A)$ be a DFA and let $q'$ be a state of $M$ called its ...
2
votes
1answer
65 views

Is there a DFA with $k+2$ states which its reverse has $2^k$ states

I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states. I am trying to find an ...
1
vote
1answer
247 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 ...
6
votes
2answers
130 views

Partition an infinite regular language into 2 disjoint infinite regular languages

Given any infinite regular language $L$, how can I prove that $L$ can be partitioned into 2 disjoint infinite regular languages $L_1, L_2$? That is: $L_1 \cup L_2 = L$, $L_1 \cap L_2 = \varnothing$, ...
2
votes
3answers
267 views

does a DFA converted from NFA always contain 2^Q states?

when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states? or if some sub-sets are unreachable then they are not ...
1
vote
1answer
70 views

NFA for right left multiplication

Given the following multiplication table how could one construct an NFA such that it accepts all strings that have a certain product (say a) ? The string "abcb" would be evaluated as (a(b(cb))) = a ...