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

2
votes
2answers
22 views

DFA to regular expression how to deal with 'sink state'

Didn't find a clear statement on this so I just want to make sure I'm right. If I have DFA with edges leading to a 'sink state' (non-accepting state we don't get out of) the edges leading to the sink ...
3
votes
1answer
37 views

What is the origin of using Q to denote a set of states in an automaton?

When talking about DFAs and NFAs as 5-tuples, it's common to use the letter $Q$ to denote the set of states in the automaton and to denote individual states with names like $q_0$, $q_1$, etc. Is ...
1
vote
1answer
47 views

How can I draw a Moore diagram for a given circuit?

I have a circuit and I should draw a moore diagram (state diagram) for that. ​ The problem is that every state can have 5 inputs and this makes the question hard for me. ​ I tried about 20 times to ...
11
votes
1answer
2k views

Can a language have more than one DFA?

For Example when we consider a DFA that allows the strings having neither sub strings 00 or 11 I can produce the following two ...
1
vote
1answer
30 views

Regex to NFA to complement

So I've found out that a regular expression $n$ symbols long converts to an NFA with $O(n)$ states, it is linear. Now to go from that NFA to the complement of the NFA, since I can't just flip accept ...
-1
votes
0answers
42 views

regular Language and nfa [on hold]

please how to proof this proposition can you give me a way to a proof : let L be a regular language that does not contain epsilon.show that there is an nfa without epsilon-transitions and with a ...
0
votes
1answer
44 views

Flipping accept states DFA vs. NFA [duplicate]

I realized that if a language L is recognized by a DFA, then flipping its accept and reject states (aka switching all the accept to reject states and all the reject states to accept) works to ...
3
votes
1answer
32 views

How Can I Recognize When to Use ε-Transitions in an NFA?

I am learning about finite automata for the first time. I am having trouble understanding the purpose of ε-transitions in an NFA, which seem to be crucial to counting the number of states in an NFA ...
1
vote
2answers
76 views

Designing a DFA for binary strings having 1 as the fourth character from the end

I came across someone else's old post here Designing a DFA that accepts strings such that nth character from last satisfies condition And decided to try it. Apparently it was a homework problem but ...
0
votes
2answers
27 views

In this example of determinising an NFA, isn't there an edge missing in the result?

I am reading a computer theory book and came across the following example converting a NFA to a DFA: My question is, would you not need an edge labeled $b$ going from the $x_4$ node on the right to ...
-1
votes
1answer
34 views

From NFA to DFA (basics)

I am trying to learn NFA to DFA. This is the original image To begin the process of converting to DFA, I started off with the start state and noticed that if the input is a 1, this means it goes to ...
7
votes
3answers
129 views

DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$

We can form DFA accepting binary numbers divisible by $n$. For example DFA accepting binary numbers divisible by 2 can be formed as follows: Similarly DFA accepting binary numbers divisible by 3 ...
0
votes
0answers
24 views

Understanding the construction of states in a deterministic finite automata? [closed]

I'm learning about the construction of DFA's in computational theory and confused as to how I know how many states a DFA should have. In the following example, the question states as followed: ...
0
votes
1answer
52 views

Why is $L=wxw^R|w,x\in\{0,1\}^+$ regular? [duplicate]

I was taught that if you can create a DFA to accept a language, then the grammar that is generating the language is regular. AND A DFA is a finite automata that accepts a language and also rejects ...
0
votes
1answer
72 views

If a machine recognizes language L, can it also recognize L*?

This is a homework question. Suppose the only accept state is the start state. My rationale for this is that L* is just the concatenations of L, so if all strings in L are accepted, then all strings ...
1
vote
1answer
40 views

why DFA to regex by two different methods differ

I was learning converting DFA to regex. I came across Arden's method which solve given DFA as follows: Ardens method Let us form the equations $q_1 = q_10 + q_30 + є$ $q_2 = q_11 + q_21 + q_31$ ...
1
vote
3answers
67 views

DFA for w|w has a length multiple of 2 or 3 [duplicate]

I am trying to create a DFA and a regex for this kind of exercise: $A = \{w ∈ \{0, 1\}^* |\text{length of w is a multiple of 2 or 3}\}$. I tried to do one for $2$ and one for $3$ and then combine ...
-3
votes
1answer
37 views

Need help understanding a decider

currently working through slides and I've noticed this which I believe to be an error. Shouldn't the two DFA's be swapped around, so that the one that reaches the accept state is with L(M)=nothing is ...
1
vote
1answer
65 views

Show this language is non-regular using pumping lemma: B = {ww | w ∈ {a,b,c,…,z)*} [duplicate]

The question I'm working from is: Prove whether or not a finite automation exists that recognises the following language: B = {ww | w ∈ {a,b,c,...,z)*} EDIT So I believe this is a non-regular ...
1
vote
1answer
96 views

What does the term “Finite” stands for in Finite State Machines?

Do we consider Pushdown Automata, Turing Machines in Finite State Machines? If we don't, then what does the term "Finite" stands for in Finite state machines, as PDAs & TMs are also defined to ...
2
votes
0answers
46 views

A string that takes a DFA from any state to a given state?

EDIT: as templatetypedef commented, this problem is to find out if a DFA has a synchronizing word (a.k.a. "reset sequence"). Given a finite state set $Q$, a finite alphabet $\Sigma$, and a transition ...
2
votes
0answers
22 views

Why we don't care about minimizing Push Down Automata & Turing Machines? [duplicate]

I never heard or read about the concepts of "Minimizing Push Down Automata or Turing Machines"? why we are not concerned about minimizing them, in general?
2
votes
1answer
45 views

Using Context free language to simulate regular expression in finite automata

Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n ...
-2
votes
1answer
42 views

DFA: Why is the transition function not a set? [closed]

The DFA is a 5-tuple ($Q,\sum, \delta, q_0, F$) where -finite set of states ($Q$) -finite set of symbols called the alphabet ($\sum$) -a transition function ($\delta: Q \times \sum \rightarrow Q$) ...
3
votes
1answer
29 views

Problem on finite state machines in the feynman textbook

I'm currently reading Feynman Lectures on Computation and got stuck in problem 3.1 which says Suppose we feed a sequence of 1's and 0's - a binary number - into a machine. Design a machine which ...
4
votes
2answers
61 views

How is $\emptyset^* = \epsilon$?

I know that $\emptyset$ is a an empty language, i.e. language containing no string. A law involving empty language is: $\emptyset L = L\emptyset = \emptyset$ It correctly states that we cannot ...
0
votes
1answer
44 views

Number of states in minimal Non Deterministic Finite Automata

What will be the number of states in minimal NFA that can be designed to accept the language $L = \left \{ \epsilon \right \}$ having a non empty alphabet set? My friends are saying that ...
0
votes
3answers
77 views

Proving/Disproving that language L is non-regular/CFL

Here are three examples of questions I run into. I'm not looking for solutions. If $L$ is CFL then $L' = \{ ww^R | w \in L \}$ is non-regular. If $L$ is non-regular then $L' = \{ ww^R | w \in ...
0
votes
0answers
13 views

regular expression identities and NFAs [duplicate]

I have these two problems about regular expressions, can you help me? 1) Prove (ab)∗a = a(ba)∗. I already proved this using induction and the definition of the kleene star * but I want to prove it ...
0
votes
1answer
92 views

Proving that two sets of strings are equal

I am stucked at this problem: Let $A=(\Sigma, Q, q_1, F, \delta)$ be a finite deterministic automaton (I.e. $\delta:Q\times\Sigma\to Q$) such that $Q=\{q_1,...,q_m\}$. Let's define foreach ...
2
votes
2answers
139 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, ...
0
votes
2answers
53 views

Regular Expression representing the following language

I am having trouble understanding how to write a regular expression for the set of words that contain at least two b's and at least two a's, where the alphabet is {a,b}. I understand that set of ...
9
votes
3answers
410 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 ...
-1
votes
1answer
44 views

“Best” automaton for a regular language

For a given regular language, there are multiple finite automata. How do we determine which one is best?
0
votes
1answer
73 views

non-deterministic finite automaton state transition table language question

I have the nfa problem below which I dont quite understand. I have been reading many slides on this but I'm having a really hard time understanding them enough to be able to complete the question. I ...
-1
votes
1answer
31 views

Algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A_1)$ and $y\in L(A_2)$

Let $A_1=(Q,\Sigma,q_0,F_1,\delta _1)$ and $A_2=(P,\Sigma ,p_0,F_2,\delta _2)$ a finite non determinustic automaons. Describe algorithm that deside if there are two words $x$ and $y$ in the same ...
1
vote
2answers
43 views

Complete finite automaton to never fail a match but either match original or up until the orginal

Suppose I have a finite automaton to match a simple string "abc" and I built some software around it to not only match the start of a string or a full incoming string, but rather to search through a ...
0
votes
1answer
81 views

How to draw a DFA for given language?

Give a finite state diagram for a DFA that accepts any word in the language $L = \{w \mid w \in \{a, b\}^* \text{ and }w \text{ alternates } a\text{'s and }b\text{’s and has an even number of ...
-1
votes
1answer
63 views

What input does this NFA accept?

I'm trying to find out what strings this NFA would accept. From what I understand, an empty string would work, as well as any string that has nothing but 0's. But for strings containing 1's, I'm a ...
0
votes
1answer
33 views

Finding an automaton with a given number of states

Define an NFA with 4 states that is equivalant to the following Regular Expression. $(01 + 011 + 0111)^*$. My main problem is that to check for a string of length 4 (...
1
vote
1answer
75 views

DFA accepts common strings, reduction to NPcomplete

$B=\{\left<M_1,M_2,...,M_k\right>\text{ : Each $M_i$ is a DFA and all of the $M_i$ accept some common string.} \}$ I'm trying to show that B is NP-complete. I know I have to reduce it to ...
-2
votes
1answer
50 views

Removing unreachable states from $M$ does not change $L(M)$

What is the idea behind proving that: Removing unreachable states from a DFA $M$ does not change $L(M)$. I don't know what cases I need consider. Consider any $w\in \sum^*$ and then check for ...
-1
votes
1answer
53 views

Programming Thompson's algorithm: How to represent a NFA?

I'm trying to create a small program that interprets a NFA to the corresponding regex using Thompson's algorithm. My question: What kind of notation can be used to express a NFA (e.g. in the form of ...
2
votes
1answer
26 views

How is (0|1|…|n) handled as a DFA?

How is n-times regex alternation operation, e.g. (0|1|...|n), handled in a DFA (MYT algorithm)? Here are the rules for the MYT also (Converting Regular Expressions to NFAs ): ...
2
votes
1answer
69 views

Deleting useless (dead) states from a finite automaton

A useless state in a finite automaton is one from which no path leads to a final state, hence no (piece of a string) is recognized out of this state. Theoretically, the algorithm to determine the ...
-1
votes
1answer
33 views

How would a finite state transducer with no output function work?

Say I have a finite state transducer, 6 tuple FST with a set of states, input symbols, output symbols, transition function, a start state, and an output function. If I combine the output function into ...
1
vote
1answer
32 views

Finding regular expression for a language with more substring of one type than from another

Take the alphabet A={0,1} I need to build a regular expression for the language with less or equal substrings 011 than 110. I tried to figure out what would be the finite automata but I'm not to ...
1
vote
1answer
130 views

What is the minimum pumping length of the following languages?

How to determine the minimum pumping length of union of two languages? How do I proceed after determining the individual pumping lengths? 0*1+0+1* U 10*1 - Here the minimum pumping length of the ...
0
votes
2answers
52 views

How to make a NFA (or DFA) from $\varepsilon$NFA?

I need to build a DFA from $\varepsilon$NFA, so first of all I assume that I need to convert the $\varepsilon$NFA to NFA and then to DFA (because I know the method of converting from NFA to DFA, and ...
1
vote
2answers
71 views

Question about ε-moves at $\varepsilon NFA$

We learning know about ε-moves at $\varepsilon NFA$ and I'm little bit confuse... If we have, for example, this $\varepsilon NFA$: and we have the word "$a$" - can we end the run at $s$? Or the ...