# Questions tagged [finite-automata]

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.

1,784 questions
Filter by
Sorted by
Tagged with
18 views

### Complexity of deciding if a DFA is counter-free

It is well-known that deciding whether an NFA or a regular expression define a counter-free/star-free language is PSPACE-complete. Does the problem become easier if I have a DFA as input? What's the ...
81 views

### $L'=\left \{w : w\cdot Drop_a(w)\in L \right \}$ is a regular language

$\Sigma=\left \{ a,b,c \right \}$. For a string $w\in \Sigma^*$, $Drop_a(w)$ is the string $w$ after we remove all occurrences of "a" from it. The question asks to show that if $L$ is a ...
• 147
1 vote
51 views

### Creating a DFA where the string should start with b and the length is 3

I'm new to automata and in my first exercise I have to construct a DFA that starts with 'b' and length=3. Two symbols (a,b). To my understanding, there are 4 possibilities {baa,bab,bba,bbb} I have ...
• 21
47 views

### Do all regular languages have a backwards deterministic FSM with one initial state and no $\varepsilon$-transitions?

There's been a question about an algorithm converting an arbitrary FSM into a backwards deterministic automaton without $\varepsilon$-transitions and a single initial state. As commenters pointed out, ...
• 1,467
135 views

### Is there an algorithm to turn any finite automata into a backwards deterministic one, with no $\epsilon$ transitions, and only one initial state?

An automaton is backwards deterministic if, for all states q, p, for all symbols a: $$(\delta(q, a) = \delta(p, a)) \implies p = q$$ (I think the right translation is backwards deterministic, but ...
• 53
40 views

### FSA for 'closure' of a language; how to represent?

Is my interpretation of this correct? I want to represent a regular language, L(B) as L(A*) where L(A*) represents the closure of L(B), as a DFA. In order to do so, would I draw a new edge from the ...
• 87
55 views

### How is L = a^2n regular if it doesn't pass the pigeon-hole principle test?

I understand that this topic has been discussed, and I have reviewed numerous posts about it on stack overflow. However, my question remains unresolved. Specifically, I am seeking clarification on the ...
• 11
50 views

### Is garbage state necessary in DFA that enforces a particular input combination?

If I have the regex 1(0+1)* for example, then should my DFA have an arrow leading away from the starting state for when the first input is 0? I see that this regex ...
• 87
221 views

### Is it possible to have intersection of L1 and L2 DFA contain states with no input edge?

I am doing a HW problem where I have L1 and L2. I did the product construction method to produce all the new states of the DFA representing L1 and L2 (the number of states in L1 times the number of ...
• 87
17 views

### Does a Moore Machine always require an output for start state?

My lecture notes show all moore machines as having an output even for q0, the starting state. This video shows a Moore machine without an output for its starting state. I understand that all Moore ...
• 87
33 views

### Lower bound states for NFAs: seeking examples and methods

We can establish some lower bounds for DFAs recognizing specific languages. For example, we can show that there exists a language $L_n$ such that every DFA recognizing it has at least $2^n$ states. ...
1 vote
47 views

### Quickly converting a regex into a minimized DFA

Is there some sort of algorithmic way to quickly convert a regex into a minimized DFA? I am able to somehow "guess" the DFA by playing around with the regex (as shown in the image, where the ...
59 views

### Proof that $ALL_{DFA} \in SPACE(log^{2}n)$

we define $ALL_{DFA}$ as: $ALL_{DFA} = \{ <A> | \text{ A is a DFA and L(A) = }\Sigma ^ {*} \}$ I'm looking for a proof that $ALL_{DFA} \in SPACE(log^{2}n)$ where n is the number of states in the ...
• 117
30 views

### Question about a grammar who generates $(0+1)^*$

On a test from my Automata theory class of last year, I have seen an excercise that gives the free context grammar $G$ with the following rules: $$S \rightarrow 0S1 | S0 | 1S | \varepsilon$$ and asks ...
55 views

### What is the name of a DFA where all long enough words are synchronizing words?

TLDR: What is the name of a DFA that satisfies the following property: "I can guarantee that after feeding the automaton $n$ random symbols it will end up at some state that does not depend on ...
• 153
140 views

### Design a DFA that accepts even length binary strings that start with 0 and must not contain substring "001"

it will reject strings such as 001, 0001, 0010, 001001 Accepts = {00, 01, 0111, 0101, ..}
93 views

### PDA for Palindrome Strings

I am studying Automaton Theory for first time and I am having problems to see if I do well some exercises and if I really finish them. For example, one exercises asks to give a PDA for all palindrome ...
38 views

• 147
43 views

### Decide if some DFA is accepted

Given Some(DFA) = {|A is a DFA and L(A) is not empty and L(A) is not equal to Σ^(*)} Show Some(DFA) is decidable. I produced the following answer and wanted to check if I am correct T="On input ...
• 1
277 views

### Do multi-acceptance/multi-language automata exist in literature?

A multi-acceptance deterministic finite state automaton is a tuple $(Q,\Sigma,\delta,q_0,T,f)$ where $Q$, $\Sigma$, $\delta: Q \times \Sigma \to Q$, and $q_0 \in Q$ are defined in the standard way of ...
• 173
1 vote
44 views

### Is it possible to construct a mealy/moore deterministic machine which gives an output (say x) for termination type languages?

As far as I know, Mealy and Moore machine are transducing machines and not language acceptors. So, can a Mealy/Moore machine, satisfying their very definitions, be made for languages which deal with ...
• 111
1 vote
86 views

### Trying to understand better the solution for $L \ regular \to L'=\left \{ xy^{R}z : xyz\in L\ , x,y,z\in\Sigma^{*} \right \} \ regular$

In this post: For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular? @Hendrik Jan have give a really good answer but I'm failing to understand it. I have looked at $L=\left \{ abc \right \}$ in ...
• 147
134 views

### Efficiently transforming non-recursive CFG into an NFA

It should be possible to rewrite a non-recursive CFG [1] as an acyclic NFA, since non-recursive CFGs represent finite languages (and thus regular a fortiori). Is there an explicit algorithm to rewrite ...
• 55
1 vote
52 views

### Searching for small finite state automata

Suppose I am given a finite state automaton A and a number n which should be thought of as much smaller than the number of states of A. Is there a good algorithm to find all (deterministic) finite ...
65 views

• 147
98 views

### NFA for a regular expression without $\epsilon$-transitions

I think I know how to convert a regular expression to NFA without requiring epsilon transitions, but I'm not sure if I'm right (I'm just using common sense to be honest, no particular algorithm in my ...
• 101
114 views

### Is matching pairs sufficient?

Book PDF: https://vishub.org/officedocs/13770.pdf Pg 253 of book This is a snapshot from Dexter C. Kozen - Automata and Computability, Lecture-35, Undecidable problems about CFLs. My question here is ...
1 vote
84 views

### Constructing a DFA that accepts the set of binary strings with an even length and an odd number of 1s

For this problem, I decided to tackle it by getting the intersection of the DFA that accepts binary strings of an even length and the DFA that accepts binary strings with an odd number of 1s (as seen ...
• 13
86 views

### Constructing a DFA that accepts the set of all binary strings that contain substrings "01" or "10"

I'm having trouble designing a DFA that accepts substrings of both 01 or 10. So far, I have constructed separate DFAs that accept the substrings "01" and "10" respectively. What I'...
• 13
46 views

### Finite state automaton

Recently, I have been trying to understand Kitaev's textbook Classical and Quantum Computation, in which he defines a (finite-state) automaton as a function $D:Q\times A'\to Q\times A''$ where $Q$ is ...
• 121
1 vote
75 views

### Finding the Smallest Language Class containing a given language definition

Given two regular languages L1 and L2 over alphabet Σ, we define the operator RQ(L1, L2) = {w | there exists a word v in L2 such that wv is in L1}. The task is to determine the smallest language class ...
• 11
50 views

### DFA for $\{s\mid ss\in L(A)\}$ [duplicate]

I've started learning automata recently, and am struggling to figure out how to find a finite automaton that satisfies the following: Given DFA $A_1 = (Q, \Sigma, \delta, q_0, F)$, find a finite ...
141 views

### in NFA is every state itself contained in set generated by transition function when considering epsilon transition from that state?

in $\epsilon$-NFA (NFAs involving $\epsilon$ transitions) when we have $\epsilon$ transitions, I understand it as where can we go if we don't read any symbol from the input tape, then I think every ...
• 359
18 views

### What is the set FirstHalves B? You can simply write out the set explicitly, enumerating the first four values

For any set of strings A, define the set FirstHalves A = {x∣∃y such that len(y) = len(x) and xy in A }. For example, FirstHalves {01, 111, 1010, 001101, 1011} = {0, 10, 001}, ie the first halves of ...
1 vote
56 views

### A proof that $a^n b^m$ for $n\neq m$ is not regular by using the pumping lemma

I am looking at $L=\{a^nb^m |n\neq m \}$. I would like to prove that $L$ is not regular. This can easily done by assuming it is regular and looking at $\overline L$, or by using other theorems. ...
• 485
1 vote
94 views

### Subset Relations Between CFGs and Their Languages

Is it possible for there to exist two context-free grammars where the set of rules of the first is a proper subset of the set of rules of the second, yet the language generated by the second grammar ...
• 15
1 vote
160 views

### Draw a finite automation for {w ∈ Σ ∗ | w does not contain the substring 10}

So I am trying to draw a finite automation that has no limits on the length, but cannot have the substring of 10 I created a DFA that could satisfy this requirement,...
• 13
90 views

### What is the regular language for L = {w | w has even length, and starts and ends with the same symbol}?

I originally thought it was 0(01)*(01)0 U 1(01)(01)1 where: two versions: one that starts and ends with 0, the other that starts and ends with 1 connected by plus, which does not mean union of both ...
• 13
50 views

### A more concise Finite Automata for 10 substring?

I am learning about finite automata and trying to create a machine that matches {w ∈ Σ∗| w does not contain the substring 10} I created a DFA where it either starts ...
1 vote
75 views

### Shortest regular expression possible

The question asks to write the shortest regular expression possible to the following automaton: I see only one way to tackle the problem: Use one of the methods mentioned here How to convert finite ...
• 147
42 views

### How to convert the following from NFA with ε-moves to DFA?

Can you provide the transition table along with the solution for better understanding?
75 views

### Construct a regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa"

I want to construct a regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa". I tried to follow the same procedure as in all the words ...
124 views

### regular expression for $\{w\in \{a,b\}^*\mid |w|_a \mod 2 = 0\}\setminus \Sigma^*aab\Sigma^*$

The question asks to write down a regular expression $r$ indicating the language of all the words above $\Sigma = \{a, b\}$ , in which the number of $a$ is even and there is no sub-word $aab$ in them. ...
• 147
1 vote
95 views

### Resources on Moore and Mealy Machines

I was studying about Moore and Mealy machines but having hard time connecting with them because 1) they are different from typical normal machines.what is the need of "output" and 2) My text ...
• 71
113 views

### DFA that accepts strings ending with an even number of 1 in the last three characters ("000","110","101","011")

I need to design a binary DFA to accept strings where the last three characters read are either "000", "110", "101" or "011". My brutal solution is: I need ...
• 11
I have to create an NFA $\mathcal{A}$ that accepts the language $L = \{w \in \Sigma^* \ | \ |w|_a \ \text{is divisible by 2 or} \ |w|_b \ \text{is divisible by 3} \}$ So the NFA only accepts words ...