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
4answers
113 views

Regular expression (ab U a)* to NFA with two states (Sipser)?

In the 3rd edition of Sipser's Introduction to the Theory of Computation (example 1.56, p.68), there is a step-by-step procedure to transform (ab U a)* into a NFA. And then the text ends with: "In ...
1
vote
1answer
39 views

Convert DFA to Regular Expression

In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The q_2 state is eliminated first. The provided solution to eliminate q2 is: ...
4
votes
0answers
64 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 ...
7
votes
1answer
64 views

Smallest NFA accepting concatenations of two words of the length $k$ which are different at all positions

Let $k\in \mathbb N$ I'm looking for a small NFA build for the language of concatenation of two words of the length $k$ which are index-wise different, i.e. $$L_k=\{u\cdot v \in \Sigma^* : ...
5
votes
1answer
103 views

Transition coverage for a DFA

Let $G$ be a directed graph, with a single source node $s$. I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where ...
2
votes
2answers
56 views

Language to Construct Finite State Transducer

I am attempting to write a Finite State Transducer module in OCaml, because I think it's a good exercise, which is because I have been teaching myself Natural Language Processing. You typically ...
-1
votes
2answers
34 views

How deciding if 2 deterministic finite automatas decide the same language? [duplicate]

Is there any polynomial procedure to decide if 2 deterministic finite automatas decide the same language?
0
votes
1answer
67 views

A DFA recognizing my name

How can I know if my DFA is implemented correctly? For example, I need to build a DFA, and then minimize it which will recognize my name. Language which describe my name is: L = {pustai, marius} I ...
2
votes
1answer
29 views

Describing explicitly the MyHill-Nerode classes created by a language

I want to practice proving a language is regular or not using the MyHill-Nerode theorm, but for that I need to be able to describe the classes. Here's my practice attempt: For the language ...
-1
votes
3answers
127 views

Problem understanding DFA & NFA equivalence in Theory of Computation

Before asking this question,I had gone through Equivalence of NFA and DFA - proof by construction but my question is a bit different from that. I was reading Michael Sipser's ...
-1
votes
1answer
40 views

Transition diagram for (b+aa*a)a*

The answer that my friend says is B, however A also accepts it. A can be DFA while B is NFA, both of them are valid. So is there any other factor using which we decide one from them? Or are both ...
0
votes
1answer
37 views

Proof that finite automata is closed under intersection

I'm looking at a proof that says that: If $M_1=(Q_1, \Sigma , q_1, A_1, \delta)$ and $M_2=(Q_2, \Sigma , q_2, A_2, \delta)$ are two finite automata(FA) then $M=M_1 \cup M_2$ is also an FA. We define ...
3
votes
3answers
59 views

generate possible inputs valid for automata

I find lots of solution where you have an Automata and a input string , you can validate whether input string is accepted by automata or not. Can we do the reverse ? I am looking for solution which ...
-1
votes
1answer
69 views

Hopcroft Book: Finite Automata Question

I'm resolving this question of Hopcroft and et al Book. Figure 1 below is a marble rolling-toy. A marble is dropped at A or B. Levers $x_1,x_2$ and $x_3$ cause the marble to fall either to the left or ...
1
vote
1answer
123 views

Draw a graph of DFA for a regular language

I'm trying to draw a DFA graph for the regular language where every chain: ...
1
vote
1answer
72 views

Turing Decidable [closed]

M = (Q, Σ, Γ, δ, q1, qaccept, qreject), where Q ={q1, q2, qaccept, qreject}, Σ = {0, 1}, Γ = {0, 1, U}, and transition function δ is as follows: ...
0
votes
1answer
42 views

Convert regular expression to Automaton

I'm trying to construct a finite-state automaton from the following regular expression: $$ (a|ba)(a|ba)^*(b|ab)^* $$ I know that from $$ (a|ba) $$ the automaton should look something like this: ...
0
votes
3answers
110 views

Build a regular grammar for a regular language [duplicate]

The language considered is the infinite set of all chains that meet the following conditions. Conditions: ...
0
votes
2answers
42 views

Recognizing a language given a Automata

I'm trying to figure out which language can be recognized in this automaton According to wikipedia here "The language L ⊆ Σ* recognized by an automaton is the set of all the words that are accepted ...
1
vote
0answers
55 views

Reducing states in a finite-state machine using compatibility classes, for an incompletely specified machine

In the process of reducing the states of a synchronous finite state machine first we need to create maximal compatibility classes (of states; which states can be compatible, i.e. the "don't cares" can ...
0
votes
1answer
50 views

Number of Final States Subset Construction for NFA to DFA

"Suppose we use the subset construction to convert a $7$-state NFA $M = (Q,\Sigma, \delta, q_0, F)$ into a DFA $M' = (Q', \Sigma, \delta', q_0, F')$ for the same language. Then $M'$ will have $|Q'| = ...
10
votes
1answer
158 views

The number of different regular languages

My question is: Given an alphabet $\Sigma = \{ a,b \}$, how many different regular languages are there that can be accepted by an $n$-state nondeterministic finite automaton? As an example, let us ...
6
votes
1answer
210 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 ...
4
votes
1answer
58 views

NFAs with more than one initial state

I'm trying to give a meaningful definition for NFAs with more than one initial state. I know from the formal definition in Wikipedia that it is possible to have more than one initial state, it ...
0
votes
2answers
40 views

Automata with no transition for some character

Given an automaton and an alphabet $\{a, b\} $, and the language accepted by the automaton is $ab^*$. Such an automata can be found here: My question is: this automaton cannot process the word ...
1
vote
3answers
140 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 ...
1
vote
2answers
136 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
71 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
252 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 ...
1
vote
2answers
36 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
47 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
172 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
42 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
60 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
245 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
81 views

Are all DFAs also NFAs?

Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?
0
votes
1answer
47 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
77 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
133 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
63 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
79 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
65 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
82 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
100 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
571 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
163 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
61 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
128 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
47 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
58 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 ...