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
1answer
33 views

NFA to accept strings where the third AND the third-last element are b

Alphabet is {a,b}, the third element from the start must be "b" (e.g: aab..., abb...) and the third-last element must also be "b" (e.g: ...baa, ...bbb). I can do them separately but at the same time I ...
-4
votes
1answer
67 views

Order classic notions of computability by power

I need some help with a question. I'm currently studying for an exam and I could therefore use some help with this following question: Order the following formalisms (but one) according to their ...
-1
votes
0answers
17 views

Convert regular expression to FA?

I am trying to solve a practice problem from my textbook which is to draw an FA from this language: L(ab* a*) U L((ab)*ba) I need help to draw the second part L((ab)*ba). I know the shortest string ...
1
vote
2answers
31 views

What is the expressive power of finite-state transducers and pushdown transducers?

One would assume that a finite state transducer can perform any translation such that the resulting string is from a regular grammar. Similarly, that a pushdown transducer can generate strings from ...
-3
votes
0answers
29 views

Theory of automata [duplicate]

You are required to construct an FA and regular experssion for the language of all those strings whose length is Odd, but contain even number of b’s defined over alphabet set {a,b}.
-1
votes
1answer
95 views

Regular expression for language of strings having odd length but even number of $b$'s [duplicate]

I have to draw a finite automaton of a language over $\{a,b\}$ of all strings having odd length and has an even number of $b$s. I already came up with following regular expression ...
-1
votes
1answer
24 views

Subsets and Proper subsets of regular language

Let L ⊆ {0, 1}* . Then 1) If all proper subsets of L are regular,is L regular? 2) If all finite subsets of L are regular,is L regular? 3) If a proper subset of L is not regular,is L non regular? I ...
1
vote
1answer
34 views

Finding the Regular Expression of a language

I'm trying to find a regular expression for the language $$L = \{w\mid n_a(w)+n_b(w)\equiv 2\pmod3\}\,,$$ where $n_a(w)$ is the number of $a$s in $w$. I can see that this would generate strings of ...
1
vote
2answers
69 views

Write a regular expression - Contains an equal number of 01 and 10 subtrings

I have this language: And ive worked on a DFA where i can move on to create the RE. Here is my DFA: What im trying to do now is using ardens theorem to get the Regular expression however I'm ...
-3
votes
0answers
12 views
-4
votes
0answers
11 views
0
votes
0answers
31 views

Minimize NFA with epsilon transition

I have an NFA with epsilon transition, I would remove the epsilon transitions, but I do not know if I have to use Hopcroft algorithm or another algorithm. Can you help me? Thanks
-3
votes
0answers
29 views

How do I produce a regex from an automaton?

I'm confused as to whether it is required that I hit the final state or not. So far, I have (011)*(0011)*00 I don't know how to account for the path 0101011 because after that sequence, then there ...
1
vote
1answer
30 views

What name for an algorithm is more correct: Kleene's algorithm or McNaughton-Yamada algorithm?

The perhaps most widely known algorithm converting finite automata into rational expressions is usually known as Kleene's algorithm. However, Sakarovitch in his book Elements of Automata Theory ...
7
votes
1answer
458 views

Is it possible to build DFA for odd-length words with 1 in the middle?

$L := \{w \in \{0,1\}^* | $the length of $w$ is odd $ \wedge $ 1 is in the middle of $w\}$ So the alphabet is $\{0,1\}^*$. My problem is that I can't keep track of the equality of chars before and ...
1
vote
0answers
53 views

Construct DFA given oracle access to the language

I was given 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 accepts or not): ...
3
votes
1answer
65 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
69 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
28 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
15 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
40 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 ...
6
votes
2answers
103 views

How similar are two DFAs? -not just binary equivalence-

Are there any measures to compute similarity (or distance) between two DFAs? If yes, which are the main references? I need a measure of similarity, not only a (binary) equivalence test. ...
3
votes
3answers
43 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
36 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
29 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
89 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
60 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
31 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
92 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
62 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
66 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
60 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
1answer
29 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
36 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
47 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
49 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
37 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
27 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
41 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
52 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
68 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
147 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
43 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 ...