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.

Filter by
Sorted by
Tagged with
1
vote
1answer
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 ...
-1
votes
1answer
38 views

What strings does this language accept/reject?

F = {ww | w ∈ {0,1}^*} Which strings are accepted and why? 0011 1010 1111
1
vote
2answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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. ...
-1
votes
1answer
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 ...
1
vote
1answer
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$...
0
votes
0answers
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)
7
votes
3answers
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 ...
2
votes
3answers
123 views

An approach to determine whether language is regular or not?

I have the following problem. I need to determine whether this language is regular or not: $L:= \{ w \in \Sigma^*: \forall \alpha ∈ \Sigma, |w|_\alpha \text{ is even or divisible by 3}\}$ $|w|_\...
0
votes
1answer
35 views

Is this a valid DFA for (a|b)*abb?

I'm trying to come up with an alternate DFA for accepting (a|b)*abb than the one present in the dragon book. Here's the one I tried: It seems valid to me but I'm ...
0
votes
2answers
38 views

How to prove this language is context free?

There's lots of ways to prove a language is not context free. Going through some exercises, I'm stuck at a question that asks me to prove that a language is indeed context free. $L = \{a^{(n+1)} b^{(...
2
votes
0answers
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 ...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 ?
0
votes
0answers
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....
3
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
-1
votes
1answer
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 ...
-2
votes
1answer
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?
1
vote
2answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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) ...
1
vote
3answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
3answers
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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
3
votes
3answers
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 ...
-1
votes
1answer
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 ...
-2
votes
2answers
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?
0
votes
2answers
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}$. ...
1
vote
1answer
49 views

Distinction between 2 languages.One is regular the other is not

whenever it needs to be determined if langage is regular or not, I use the notion that it is impossible for a machine to "remember" an infinte states. given 2 languages:$L_1=\{(01)^{n}(10)^{n}|n \in \...
3
votes
1answer
44 views

Slowest growing upper bound for the minimum length of a complementary prefix regular expression

A postfix regular expression acting on a binary alphabet (specification from this post) can be described using the following grammar, ...
0
votes
0answers
34 views

What unusual property does this finite automata yield?

I'm asked to construct a finite automata for a given task. The Automata should accept the values zero or one. In the starting ...
0
votes
1answer
106 views

What does {a,b}* for DFA's mean?

For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has? For example a DFA that accepts $\{w \in \{a,...
1
vote
2answers
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 ...
15
votes
2answers
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.
1
vote
1answer
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 ...
1
vote
2answers
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 ...
0
votes
0answers
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?
1
vote
1answer
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 ...
2
votes
1answer
132 views

How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?

I am struggling to answer the following question: How many different languages over the unary alphabet {a} are recognized by 2-state DFAs? According to the textbook, the hint was to first ...
11
votes
2answers
3k views

Can a DFA have an unreachable state?

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 ...

1 2
3
4 5
28