# 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,356 questions
Filter by
Sorted by
Tagged with
44 views

### FA for |w| divisible by 3 or number of zeros divisible by 2

Working on a question were I should construct a deterministic finite automaton for the language $L=\{w\in \{0,1\}^* \mid |w| \mod 2 =0 \lor |w|_0 \mod 3 =0 \}$ The DFA for the two sublanguages is ...
38 views

### What strings does this language accept/reject?

F = {ww | w ∈ {0,1}^*} Which strings are accepted and why? 0011 1010 1111
312 views

### Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?

I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the ...
41 views

### Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states?

Given an alphabet $\Sigma$, let $c=|\Sigma|$. Can a set of languages $\{L_k\}$ be created, such that any DFA for $L_k$ has $\Omega(c^k)$ states and a NFA for $L_k$ exists with $O(k)$ states? I'm ...
150 views

### Convertion from NFA to DFA

I have converted nfa to dfa. But when I checked with some examples, it looks like it is wrong. ...
53 views

### Prove that a language is decidable

I need some help to prove that the language is decidable. $K$ = {$N$ : $N$ is a DFA (Sigma = {a, b, c}) and $L$($N$) contains at least one word in which there is no a}. It tried to make an algorithm ...
18 views

### Clarifying Practicality and Usage of a DFA's Accepted Language

I was reading up on DFA's and their accepted languages when I stumbled across this: Let a DFA $M$ accept the language $L⊆Σ^∗$, DFA $M'$ accepts $P(L)=$ {$w∈Σ^∗|wy∈L$ for some $y∈Σ^∗$}. Since any $wy$...
14 views

### Prove if {a^i b^j | i ≤ j} is a regular language or not [duplicate]

How can i prove if this language is regular or not? (i think is non regular)
1k views

### Why does a DFA have multiple final states?

I am taking a course on programming language design and we got to the DFA part. It is known to be formally defined by a 5-tupple but they did not make it very clear to us why a DFA can have multiple ...
123 views

36 views

### can a DFA with only final states be minimized?

I need to construct a DFA for a certain language with as little states as possible. so far my "best" solution contains 15 states. however, people claim it is doable in 7 states only. I tried for ...
56 views

### Usual distances on DFAs (Deterministic Finite Automata)?

I've been searching in the literature for examples of distances defined on the set of the DFAs (or on the set of minimal DFAs) that are defined on a given alphabet sigma. Since the languages they ...
43 views

### Prove that regular languages are closed under Kleene star [duplicate]

Given $L$ is a regular language, how can I prove that $L^*$ is a regular language too? I've constructed an NFA which contains a new initial state that has an $\epsilon$-transition to the original ...
43 views

### Minimizing DFA built on set of words

A set of English words is given. Is there linear or sublinear algorithm to build minimal DFA for the given dictionary? I tried different approaches, and they all were concerned with building Trie and ...
12 views

### How to write regular expression [duplicate]

The set of all strings over {0,1} such that every block of 4 consecutive symbol contain at least two 0's Can you guys tell me what is the correct answer for this ?
60 views

### McNaughton-Yamada Algotihm (1960) Regular Expression to DFA without passing through NFA

I have a homework problem here. It asks me to use the McNaughton-Yamada algorithm to first convert a regular expression to a DFA, and then minimize this using a partition argument. I can do the latter....
135 views

### Arden's Rule, DFA & NFA to regular expressions

I have been trying to figure out the Arden's Rule and the equational method to transform DFA's & NFA's to RE. I know what the rule state: if x = s + xr then x = sr*, with $s,r\in$ Regular ...
18 views

### Why are MM-1QFA strictly more powerful than MO-1QFA?

While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97); both ...
110 views

### Prove the following language is regular?

Assume $L_1$ is a regular language, and define: $$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$ Show that $L$ is regular. I first tried to prove by showing that the ...
35 views

### Is this FA really equivalent to the given regular expression?

From the picture, the automata can accept $(\text L|\text D)^*$ following say $\_\text L\text D$, but in the formula above $(\text L|\text D)^*$ can't follow the $\_\text L\text D$. So the Automata ...
43 views

### Design a DFA recognising the following language

Design a DFA over alphabet (a,b) such that for all it's string no prefix contain two more a's than b's and two more b's than a's and the number of a's is equal to b's. Is it possible to design a DFA ...
71 views

### Design a DFA for the language L = {w | w contain 2 a’s at any position and greater than 3 b’s at any position, w ϵ {a.b}*}/

I do not understand this question,because for saving Number of a's and b's memory is required,which FA does not provide.could anybody please explain this?
66 views

### DFA for binary language with constraints on triplets

I need to create a deterministic finite automata whose language consists of words over $\{0,1\}$ of any length, satisfying the following constraint: Among any subsequent 3 numbers, there needs to ...
38 views

### Finite State Machine with limited operations

I have to implement a state machine in some special hardware which has a lot of limitations. This hardware can be understood as a box that gets events as inputs and could output events. The state ...
72 views

### Converting DFA to Regular Expression Using State Removal

I'm trying to convert the following NFA to a regular expression. I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
51 views

### NFA-$\epsilon$ extended transition function for inverted strings

It is well known that in $NFA-\epsilon$ the extended transition function is defined as it follows: \begin{align*} \hat\delta: Q &\times \Sigma^* \rightarrow \mathbb{P}(Q) \\ \hat\delta(q,\epsilon) ...
192 views

### Large DFA to regex?

For an assignment for one of my courses, one of the questions is to provide a regular expression for the language: "the set of strings such that the number of 0’s is divisible by six, and the number ...
36 views

### Constructing Noneterministic Finite Automata (NFA) with a “not” condition

I have a question about some theoretical CS. Particularly, designing an NFA diagram (nondeterministic finite automata) from some conditions. I think I understand how to construct NFA's under most ...
64 views

### Minimization of DFA- one state mark or no mark?

I want to know, what if the DFA is merged states. So if my DFA starts with q0 and then have (q0,q1) state it goes to with an 'a' for example. How do I do the table filling method. I tried to rename ...
152 views

### Prove that a language is regular

I'm working on an example which says that a string x is obtained from a string w by deleting symbols if it is possible to remove zero or more symbols from w so that just the string x remains. For ...
59 views

### Is it possible to constract Moore or Mealy machine with a different size of input and output?

Is it possible to constract Moore or Mealy machine to take input tape: 0011 and output: 00001111 (or vice versa). In other words, input and output have different size. I want to construct FSMs to ...
168 views

### Why does this NFA having an empty symbol

I'm trying to understand the difference of DFA from NFA I have this example in my coursebook Are the empty symbols at the start necessary? or can we do away with them to have something like this
176 views

### What are some uses of the Thue-Morse sequence in computer science?

Note: I come from a mathematics background. The Thue-Morse sequence $t_n$ is a binary sequence that takes the value $0$ at the positive integer $n$ if the number of $1$s in its binary expansion is ...
97 views

### Constructing an NFA for a language defined over $\Sigma = \{0, 1\}$

The language is defined as $$L = \{0^n10^m10^q \mid n,m,q \in \mathbb{N}, q \equiv nm \mod 5\}.$$ Can someone help me get started on this question? I don't know what part of the question I should do ...
211 views

### Is the set of strings with equal number of 010’s and 101’s regular?

Let the language be defined over alphabet{0,1}. Can you prove this by pumping down?
44 views

### Construct a PDA for at least one $w_i$ $\neq$ $w_{i + 1}^r$?

My assignment asks Let $S = \{ w_1\#w_2\# \dots \#w_k | k ≥ 2; (∀i ≤ k)w_i ∈ \{0, 1\}^\star ; (∃i < k) w_i\neq w_{i + 1}^r$ , i.e., not every string $w_i$ is equal to the reversal of $w_{i+1}$. ...
49 views

40 views

### In an NFA that recognizes L(ab) where ab is a regular expression, what is the point of the empty string transition?

I'm reading Introduction to Computational Theory by Michael Sipser. He provides the NFA below as one that recognizes the language of the regular expression $ab$. What is the purpose of the middle two ...
5k views

### Can a deterministic finite automaton ever go into an infinite loop?

As the title suggests, is this possible? Or does it halt execution when it hits the trap state? Thanks to anyone who can clear this up.
47 views

### Design a DFA that recognizes the following language

My assignment asked to design a DFA that computes the language: $L = \{ w \in \{a,b,c\}^\star | \#_a(w)$ is even, $\#_b(w)$ is odd, $\#_c(w)$ is even} I have been stuck on this question for 2 ...
163 views

### How Intersection of Regular Language and a CFL is a CFL?

CFL is not closed under intersection. That means, if we have L1,L2 of CFL then L1 intersection L2 is not a CFL And we know, all Regular languages are CFL. Then ...
48 views

### What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?

It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?
70 views

### How specifically do I need to describe (in words) the language of a regular expression?

For the regular expression $(a^*ba^*b)^*a^*$, I want to learn how to describe it in words. I know there are an even number of $b$s but how much do I need to explain it? Do I need to explain it enough ...
I am trying to prove or disprove the following statement: If $A = (\Sigma, Q, \delta, q_0, F)$ is a complete DFA where $F \neq \emptyset$ then $L(A) \neq \emptyset$ So my initial thinking is to ...