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)

1
vote
0answers
15 views

Construct DFA given oracle access to the language

I was given a question the following question. Given a minimal DFA $A$ with $m$ states over some alphabet $\Sigma$ which is a "black box" (you can only run words to it and it tells you if it ...
3
votes
1answer
52 views

Where Can I Find DFA Practice?

Where can I find a web site or book where I can practice drawing DFAs from a language like " {w| w has at least three a’s and at least two b’s} ". It will be important to have access to the answer so ...
0
votes
2answers
61 views

If L is a regular language, how to prove that L' is also regular?

I've been trying to construct a proof of the following statement the whole day but I got stuck: If $L$ is a regular language, the language $L_{}{'}$ consisting of all words in $L$ containing the ...
0
votes
0answers
24 views

Is the language of all DFAs that accept the empty language regular?

Is $E_{DFA}$ in the class of regular languages? $\qquad E_{DFA} = \{ \langle D \rangle \mid D \text{ is a DFA }, L(D) = \emptyset\}$ My argument is that it is because all of the DFAs in $E_{DFA}$ ...
1
vote
1answer
14 views

What is the effect of having a transition in an epsilon-NFA upon “$\epsilon$,0”?

When a transition between two states is achieved via any of the symbols $\epsilon,0$, how does the $\epsilon$ effect the transition between the two states? Does it simply mean that the $0$ is ...
1
vote
2answers
27 views

similar language by two DFA then why wrong answer

I attempted a mock paper for finite automata .so i was asked to create a DFA which accepts a language in which inputs are a,b and number of b's should be divisible by 3.The first image is my answer ...
1
vote
1answer
30 views

Design the grammar for the following [closed]

Design the grammar for the following: L = (a^n)w(w^r)(b^n) where n>=0 and w={a,b}
6
votes
1answer
36 views

What does Cellular Automata Pre-image problem actually means?

I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata. In the 2nd page he lists three NP-Complete ...
1
vote
1answer
31 views

How similar are two DFAs? -not just binary equivalence- [on hold]

Are there any measures to compute similarity (or distance) between two DFAs? If yes, which are the mainly references? NB: I need a measure of similarity, and not binary equivalence test.
2
votes
2answers
31 views

What is the difference between finite automata and Büchi automata?

as the title suggests, I was struggling to define the differences between finite and Büchi automata and how they are represented. From an assignment I'm working on, this automaton can be depicted ...
-1
votes
1answer
31 views

construct a dfa that accepts odd consecutive number of 0's and 1's

this dfa should accept only consecutive odd number of both 0's and 1's. example: 10001,1110001,10,01,011101. How can I draw its diagram?
0
votes
1answer
23 views

Isomorphism of a DFA and the minimal DFA

I have a DFA A, I minimize A and the minimized DFA obtained is M. My question is if in general A and M are isomorphic?
0
votes
3answers
86 views

Design an NFA to accept a, ad, abc, abd, but not e, abcd?

I've made the following diagram to accept a, ad, abc, abd but I don't it to accept e, abcd, how can I limit that? Updated I modified the diagram in another attempt:
1
vote
1answer
49 views

PDA for all non-palindromic strings of even length

I had a homework assignment where I had to build a PDA over the alphabet $\{a,b\}^*$, accepting $L = \{x \mid x \text{ is even but not a palindrome}\}$. I already turned it in, but I know I had it ...
1
vote
1answer
28 views

Removing $\epsilon$ transitions in a NPDA

NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions. However, NFA's with $\epsilon$ transitions could be converted to those without any ...
1
vote
1answer
90 views

How do I describe a DFA?

Consider the alphabet E = ${[abc] : a, b, c \in 0,1,...,9)} $ Example [234], [567], [897] are symbols of the alphabet. For a string $w \in $ let n(w) denote the number represented by $ w $: ...
2
votes
3answers
56 views

Proof that whether a regular language is finite is decidable

I have this question for a homework. The question stems from the fact that you can determine whether a regular language is empty by using a Turing machine to count the states n in the given FSM. When ...
-1
votes
1answer
56 views

Show that if S is an arithmetic progression, then A can be recognized by a DFA [duplicate]

A set S of nonnegative integers is called an arithmetic progresion if there exist some integers n and p such that S = {n + ip : i ≥ 0} Let A ⊆ {a}∗ and consider S = {| x |: x ∈ A}. (1) Show that if ...
0
votes
0answers
28 views

Regular expression for C-style /**/ comments [duplicate]

I am aware that a similar question was already asked here and that the recent question A DFA for recognizing comments is also related but I am not satisfied with the answers. The point is that ...
3
votes
3answers
57 views

Regular expression for a binary string containing even number of 0's

To get the regular expression I made a finite automata as the following (not sure if you can directly write regular expression without it): The regular expression for the above according to me ...
-1
votes
0answers
15 views

NFA recognizing a string from a 4-letter alphabet with last letter appearing only once [duplicate]

How can I construct an NFA that accepts the language $L=\{w\in\{a,b,c,d\}^* : the\ last\ letter\ appears\ only\ once\ in\ w\}$
-1
votes
1answer
27 views

Why do these NFAs need epsilon transitions?

In the picture below, I'm trying to figure out why there's a need of epsilon in there and what would be the difference if we didn't put epsilon.
2
votes
1answer
34 views

Difference between a minimal DFA and a canonical DFA

given a language L,a DFA M that recognize L is minimal if M is the DFA with the minimum number of states. In order for this to happen M does not have neither unreachable nor equivalent states. The ...
1
vote
1answer
50 views

Regular expression for a finite automaton appears to be wrong

For the following finite state machine: The language recognized by it is given to be: $0+(10+11)(0+1)^*$ in my samples book, which I think is clearly wrong, since there's no return path to the ...
2
votes
1answer
41 views

How to write the turing machine processing operations?

I have this Turing machine example given in my book: For the language $0^n1^n$. I understand how it works because it's very similar to a Finite State Machine. But what I want to know is the ...
0
votes
1answer
48 views

If L is a regular language then the language replace(L,σ,τ) is also regular

I am stuck at the following problem: Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular. ...
-3
votes
1answer
16 views

Equivalence of DFA' definitions

According to wikipedia DFA accepts word $w$ by one of two definitions: A word $w$ is accepted by $M$ if $\hat\delta(q_0,w)\in F$. A word $w=w_1w_2\dots w_n$ is accepted by $M$ if $\exists ...
0
votes
1answer
36 views

What happens when ε-clos(X) contains duplicate elements? Example: (1+0)*1

I am learning about state machines from the Stanford online cs143 course. Here I have tried to build a nondeterministic finite automaton for the regular expression ...
2
votes
2answers
34 views

Closure under reversal of regular languages: Proof using Automata

I have been studying the closure properties of regular languages, referencing the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman. Under the ...
1
vote
1answer
26 views

A regular expression for an automaton which accepts strings with no more than 3 consecutive zeros [duplicate]

This is the automaton I want to find the regular expression for: As you see, states Q1 to Q4 are accepted and Q5 is a kind of trap. This automaton accepts strings that have no more than 3 ...
3
votes
2answers
39 views

An NFA with no equivalent DFA with fewer than $2^n$ states: Example and Proof

I have been following the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman. I came across the following topic titled Bad Case for Subset ...
-1
votes
1answer
49 views

Can a DFA just have one state that is both the initial state and the final state?

so im trying to create a DFA for a language that has an infinite number of possible strings over the alphabet {a,b}. can i not just have one state (initial and final state) that loops a,b to itself? ...
3
votes
1answer
66 views

How many languages exist over a finite alphabet?

I'm currently reviewing my Automata and Languages Theory course and I stumbled upon the following exercise exams. Link In "Exercises for ACS 1, Fall 2004, sheet 1", exercise 1 item C, the question ...
4
votes
1answer
133 views

Brzozowski algebraic method for NFA

Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA some nodes have multiple in/outgoing edges single start state there might be multiple final states a state ...
0
votes
1answer
36 views

How can I prove that a Regular Language is closed under Union given two languages with different alphabets?

I need some help to prove that a Regular Language is closed under the union, using a DFA with two differents alphabets.
1
vote
1answer
25 views

How can a distributed system cooperate to determine rules of its environment?

I'm sorry if this question is silly or elementary. I'm not a computer scientist so I don't know the vocabulary to use to ask this question. Thus I've produced an analogy to explain the challenges I'm ...
0
votes
0answers
19 views

What is the difference between Moore's algorithm and partition refinement algorithm for DFA minimization?

Both the algorithms use the partition method to minimize the DFA. I cannot understand the difference between them. Can someone give an example where we can see the difference between them.
-3
votes
1answer
34 views

State machine that multiplies a binary number with a constant

I'm trying to create a FSM that multiplies a bitstream with a constant value (e.g 3). I don't have a clue how to design such a FSM. Any hints?
1
vote
1answer
33 views

Is there a complexity metric for finite state machines?

I'm working on evolving Turing machines (with binary symbols / infinite tape) for simple operations (e.g. sorting) using genetic algorithms. I'm interested in using the complexity of the FSM for each ...
0
votes
1answer
19 views

Does preparing min DFA by combining equivalent states always result in min DFA

I know the following fact: If $Ma_N=\{w:n_a (w)=Nk,k≥0\}$, then Number of states in $$Ma_{N1}×Ma_{N2} =Ma_{N1}∪Ma_{N2} =Ma_{N1}∩Ma_{N2} =Ma_{N1}-Ma_{N2} =LCM(N1,N2)$$ where $n_a (w)$ is the ...
6
votes
3answers
239 views

Why should we study all the three forms of representation of finite automata?

DFA, NFA and epsilon NFA all the three allow us to represent a particular regular language. With any of those representations we can arrive to the same regular expression, then why do we need to study ...
3
votes
2answers
34 views

How do cycles of non-consuming transitions in NFAs influence their halting properties?

I am in a class that is going over NFAs. The way they are described is a set of states, one of which is the start state, zero or more are accept states, and one or more transitions between them, which ...
1
vote
1answer
241 views

Finite State Machine that only accepts strings with equal number of 0's and 1's

Question: Suppose you have a finite state machine that accepts only strings with an equal number of zeros and ones. Show that you can then construct a finite state machine that accepts only strings of ...
-1
votes
2answers
49 views

DFA for $L_1={w:(n_a(w)+2n_b(w)) mod 3<2}$ and $L_2=\{w:(n_a(w)+2n_b(w))\text{mod 3}<2\}$

I stumbled upon this file on scribd, which gave some interesting problems on constructing DFA. So I went on solving them, until I came across one for which result DFA is not drawn but are described in ...
0
votes
1answer
32 views

Are accepting states and unaccepting states distinguishable?

Is it true that for all DFA that if $A$ is an accepting state and $B$ is not, that $B$ is always distinguishable from $A$. I don't think it's true, just because I think I can create a DFA. $B$ reads ...
0
votes
1answer
23 views

Question about DFA for exact string matching

In the Handbook of Exact String Matching algorithms, it describes the transition set for a basic string matching automaton as: for q in Q (q is a prefix of x) a in $\Sigma$ (q, a, ...
3
votes
1answer
77 views

Index of a language and its reversal [duplicate]

The index of a language is the number of Myhill-Nerode classes that it has. It is also equal to the number of states in the minimal DFA for the language. What is an example of a language that has a ...
0
votes
0answers
15 views

Proving right quotient of two languages [duplicate]

I know that if a language $L_1$ and a language $L_2$ are regular, then $L1/L2$ is regular. When we construct a DFA $M'=(Q, \Sigma, \delta, q_0, F)$, for each state $i$ we can make $i$ the start ...
2
votes
2answers
110 views

Is it legal to draw an NFA with fewer nodes than what I normally see?

Is it Ok to express an NFA accepting 1*0 like the one above? All examples in books are represented like the bottom one. I'd like to know is that only a convention or it must have two extra nodes?
1
vote
1answer
39 views

regular expression to accept all strings other than one containing ads or adlib [closed]

My intention is to select only those packages whose name do not contain adlib or ads. But if i add *adlib* and *ads* it selects all packages containing the ...