As of May 31, 2023, we have updated our Code of Conduct.

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
0 votes
1 answer
734 views

epsilon-NFA to DFA conversion - What will be the final states and do we need to create empty state in DFA?

Source of this question and problem: https://www.javatpoint.com/automata-conversion-from-nfa-with-null-to-dfa This is the question: So in this figure there are my 1 confusion-: Don't we need a empty ...
ladhee's user avatar
  • 37
0 votes
2 answers
2k views

When you convert epsilon NFA to NFA, how do you decide the final states of resultant NFA?

The question is-: THIS is the transition table for NFA-: Final result as shown in youtube video. https://www.youtube.com/watch?v=GjLiXk0imi0&list=PLENQMW_c1dimRCKF3bjUqHaH8dvJkapSw&index=49 ...
ladhee's user avatar
  • 37
-2 votes
1 answer
58 views

What does DFA that accepts at least 1 a or at least 1 b mean?

What are the language accepted by this DFA? The truth table of OR-: But I am unable to deduct what this dfa will accept? Say-: P=at least 1 a Q=at least 1 b So DFA should accept both ab. Or in ...
custep's user avatar
  • 9
0 votes
1 answer
1k views

Regular expression for set of all strings containing no 3 consecutive 0s?

The answer is $1^*01^*01^*+1^*(0+00+\in)1^*$ If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice? How do I understand what the regular ...
custep's user avatar
  • 9
1 vote
2 answers
227 views

NFA has power to be in several states at once implies NFA has ability to guess about its input. How?

I agree that NFA has power to be in several states at once. It probably means that on same input, NFA can be on multiple states. But what I can't understand is how can we conclude from this that "...
silfeg's user avatar
  • 51
0 votes
1 answer
719 views

DFA for {w|w contains a substring of length at most 5 that has at least three 1's}

I have thought about this problem, but cannot come up with a convincing answer since I think this problem has too many states too consider. The accepting states can be length 5 substring and 3 1's, ...
Sophie's user avatar
  • 1
1 vote
0 answers
111 views

conversion of epsilon NFA to NFA

I was given below task: Eliminate Epsilon-transitions in below automata My solution: Is it correct that stage 1 is actually one of the final stages? How does it work in given example? We have ...
crystalsky's user avatar
1 vote
1 answer
38 views

conversion of NFA to DFA (omitted states)

I've been given following task: Determine the following nondeterministic automaton (omit unreachable states, if they appear during construction) My solution to this: Would like to ask for a ...
crystalsky's user avatar
0 votes
1 answer
50 views

Problems with simulating NFA with DFA

I have this NFA: I want to simulate it with a DFA, thus I have the states {1}, {2}, {3}, {1,2}, {1,3}, {2,3} and {1,2,3}. Usually I look at every state and find out in which state I could end up when ...
Connor Kolan's user avatar
0 votes
1 answer
71 views

Need help with constructing a DFA

I am trying to construct the DFA that accepts the following language $$ L_2 := \left\{ w \in \{a,b\}^* \mid \#a(w) \text{ is divisible by } 3 \text{ and } \texttt{babbab} \text{is a substring of } w \...
leetdeadly's user avatar
1 vote
1 answer
60 views

What is the difference between these 2 dfas for binary strings ending with 00?

The first one is from unreputed youtuber whereas second one is from reputed university called adiuni course of theory of computation. Now I know what that second figure means, it means it also accepts ...
silfeg's user avatar
  • 51
2 votes
1 answer
233 views

Are Nondeterministic Finite Automata not allowed 'sink-states'?

By definition are Nondeterministic Finite Automata not allowed a 'sink-state' (non-accepting state we don't get out of)? I can see us having them for NFA but not necessary but do not see how they are ...
rocktarmadeyah's user avatar
2 votes
1 answer
158 views

How to verify-: A language over Σ is also a language over any alphabet that is a superset of Σ?

Context-: A language over Σ need not include strings with all symbols of Σ Thus, a language over Σ is also a language over any alphabet that is a superset of Σ. https://www.univ-orleans.fr/lifo/...
vnhc5's user avatar
  • 23
4 votes
4 answers
311 views

Are there any programming languages that support state machines in their standard library?

State machines are a fundamental computer science concept and in many senarios they are the simplest way to implement a process or program. However, most programming languages don't support them ...
Blank's user avatar
  • 141
-1 votes
1 answer
329 views

Design a DFA that accepts numbers whose sum of digits is $2 \mod 3$

Design a DFA that accepts language $$L = \left\{ x \in \{ 0, 1, 2 \} : \text{ sum of digits in } x \text{ is } 2 \mod 3 \right\}$$ How to make a DFA for this? I have no idea how to solve this dfa ...
axhbagi's user avatar
-3 votes
1 answer
307 views

Design a DFA that accepts language L={ x in (0,1)* | the third bit from x from its right end is 1}

this is very confusing question. I am having no idea to solve it, can you please guide me here?
jovlea's user avatar
  • 19
0 votes
1 answer
1k views

DFA for even number of 1's

My attempt at solution-: Solution by a teacher-: Both are giving same answer, is the one that I made correct?
axhbagi's user avatar
-2 votes
2 answers
671 views

Prove that the class of regular languages is closed under three operation

We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this ...
kangkang's user avatar
0 votes
1 answer
217 views

Prove the class of regular languages is closed or not closed under the operations below

Suppose $A$ and $B$ are both languages over $\Sigma=\{0,1\}$. We use $n_0(x)$ and $n_1(x)$ to represent the number of $0$s and $1$s in the string $x$ respectively. Consider the following two ...
scone's user avatar
  • 3
0 votes
1 answer
268 views

Size of minimal DFA

Assume a given NFA for a regular language with $n$ states. It is clear that determinizing it may result in an DFA with $\Omega(2^n)$ states. However, the minimization might decrease the number of ...
Michal Dvořák's user avatar
1 vote
2 answers
310 views

What is the minimum pumping lemma length of $01^*0^*1$?

I've taken the following steps to prove that the minimum pumping length (PL) of the above language, $L= 01^*0^*1$: Set a PL. I chose $p=2$ Choose a string from $L$ where $|w|\geq p$, I chose $w=011$. ...
askman's user avatar
  • 113
0 votes
0 answers
61 views

If $L$ is regular, is $L/w = \{x\mid wx\in L\}$ regular?

I'm trying to see if the language $L/w = \{x\mid wx\in L\}$ is regular given that $L$ itself is regular. It seems to me that if $L=L(A)$ for the NFA $A = (Q, \Sigma, \delta, S, F)$, then the NFA $A'$ ...
Lt. Commander. Data's user avatar
2 votes
2 answers
65 views

If L is regular so is the language of compressed doubles

Suppose L is a regular language over the alphabet $\Sigma$. I need to prove that $$ L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\}$$ I thought I could take a DFA which computes ...
Addem's user avatar
  • 303
0 votes
2 answers
427 views

Regularity of CFG and DCFL

I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$. My ...
Alok Maity's user avatar
0 votes
1 answer
197 views

How to convert this regular grammar into a finite state automaton?

In a French course (p. 13) there is a language of words of {a,b,c} containing at least one occurrence of the string bac. The ...
Amessihel's user avatar
  • 103
1 vote
1 answer
192 views

Correct complement of a regular language when the union of the languages do not lead to entire set of strings over the given alphabet?

I have a question that says that the complement of a regular language given as: $L_1=\{a^nb^m|(n+m)<5\}$ is $L_2=\{a^nb^m|(n+m)\geq5\}$ over $\Sigma=\{a,b\}$, and therefore, we can simply construct ...
Userhanu's user avatar
  • 137
1 vote
1 answer
310 views

Designing a NFA that accept the set of strings that contain an even number of substrings 01

I'm new in theory of computation. Here {0,1} set of input symbols. I tried to make the NFA from L(M)= set of all accepted strings, but unable to complete it. Can someone give some hints that how ...
Rainbow's user avatar
  • 11
4 votes
2 answers
102 views

Is the language "substrings of a regular language that are over half the length of the superstring" regular?

We say $x$ is a majority substring of $y$ if $y \in \Sigma^* x \Sigma^*$ and $|x| \geq \frac 12|y|$. If $B$ is a regular language, is the set of majority substrings of $B$ regular? I was provided the ...
Terrence Corde's user avatar
1 vote
1 answer
519 views

What is the regular expression for the language, {w | w does not contain the substring 11}

{w | w does not contain the substring 11} What I am thinking: $(0^* 1 0^* )^*$ Is anything wrong with my expression? Thanks in advance for your help!
Geoffery Quansah.'s user avatar
0 votes
2 answers
37 views

Existence of infinite unique FSAs

It is reasonably simple to show that there are an infinite number of different finite state automata that can be constructed, but has it been proven if there is an infinite number of unique finite ...
bobbin's user avatar
  • 3
3 votes
2 answers
630 views

(How) Can I remove a word from a DFA?

As the title says, is it possible to remove a word from a DFA? One obvious way is to calculate the language without the word that I want to remove and then construct the DFA for the updated language. ...
phan801's user avatar
  • 626
-2 votes
1 answer
643 views

I want to know the difference between DFA and FSA

Taking a class named Theory of Computation. Learned about Deterministic Finite Automata and just got introduced to Finite State Automata. I can't figure out the difference, are they just synonyms? ...
Abhishek Yadav's user avatar
3 votes
1 answer
631 views

Can a non deterministic finite automaton go into infinite loop?

Here is the exact same question but on deterministic finite automaton. The case for deterministic finite automaton is simple. For each state only one transition is possible for each input symbol and ...
Abhishek Ghosh's user avatar
0 votes
1 answer
75 views

Simplifying the Language of this DFA

Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
PDK's user avatar
  • 46
2 votes
1 answer
73 views

Implication of the Pumping lemma

I'm reading Hopcroft and Ullman's '79 edition of "Introduction to Automata theory, Languages, and Computation". In chapter 3, the authors say "The lemma[sic] does not state that every ...
Harikrishnan R's user avatar
1 vote
0 answers
49 views

What if have a algorithm that could generate a NFA of 42 states of any binary string of 2^32 length?

For example, if we have a true algorithm that could generate any NFA of at most 42 states from any binary string of 2^32 length. So, this algorithm can not just recognize the string but just recreate ...
samleo's user avatar
  • 11
1 vote
1 answer
53 views

Find a transducer that maps a given deterministic process to another

Let $S$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $\mathcal{A}$ and $n$ hidden states, ...
AG1123's user avatar
  • 111
1 vote
2 answers
214 views

Can a non-deterministic finite automaton die out before reading the entire string?

I am new to automata theory and have a problem that I want to solve. We have to design an NFA that starts with "ab". I have the solution and it is given by: However, my problem is: If the ...
Userhanu's user avatar
  • 137
2 votes
2 answers
205 views

Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $

I read this site example 12 that {${xww|x,w∈(a+b)^*}$} the set of strings generated by language $L$ is {${ϵ,a,b,aa,ab,ba,bb,aaa,…}$} by taking always $w$ as $\epsilon$ and $x$∈$(a+b)^∗$. But my ...
Alok Maity's user avatar
1 vote
0 answers
288 views

Intuition for the reason this language which has equal number of 01 and 10 as substrings can be accepted using bounded finite states

Firstly I don't have CS or DFA/NFA background knowledge about their theorems or lemmas, so I don't understand some related questions' answers like here. However, I can easily intuitively understand a ...
mohottnad's user avatar
  • 315
0 votes
0 answers
99 views

Are the regular expressions equivalent?

Is the following equivalence true? $$(r_1^*r_2^*)^* = (r_1 + r_2)^*$$ I think these are equivalent since both the expressions generate the same strings: $\{\epsilon,r_1,r_2,\dots\}$ etc.
Anshika Singh's user avatar
4 votes
2 answers
496 views

Why are Regular sets not closed under infinite unions and intersections? [duplicate]

Why are Regular sets not closed under infinite unions and intersections, with my flawled reasoning I came to a conclusion that since infinite unions can have no relationship between strings of a ...
Pawan Nirpal's user avatar
1 vote
0 answers
32 views

Has anyone seen the following string classifier discussed?

The closes related question I have found for this is Find string patterns preferably in regex for string streams, but it has no answer and is also a little less constrained as my idea. Given a set of ...
Gunther Schadow's user avatar
2 votes
1 answer
82 views

Minimal state DFAs for a regular expression of length $n$

I know that given any regular expression, we can find always find a minimal DFA which accepts the language it describes. However, this process can take up to exponential time and space. I'm wondering ...
Ari's user avatar
  • 1,601
0 votes
1 answer
111 views

Convert a PDA with transition for a state to itself to another PDA

Suppose we have PDA (same for DFA and Turing) that has a transition from a state to itself. Can we convert this PDA to another one without any transition like this? EDIT (My thoughts): I guess we can ...
Kurosh Ghanizadeh's user avatar
-1 votes
1 answer
53 views

Prove $(aa^*bb^*)^*=ϵ+a(a+b)^*b$ using regex laws

I tried to prove this by starting at RHS: $$ϵ+a(a+b)^*b = ϵ+a(a^*b^*)^*b$$ But I dont know how to convert $(a^*b^*)^*$ to something else that will be helpful. Any ideas?
Nameless's user avatar
  • 163
-1 votes
1 answer
29 views

How can I implement a Deterministic finite automaton which accepts

Problem: implement a Deterministic finite automaton which accepts 01 ∪ (2∪10*2)* ∪ <- is union symbol I have a lot of problem trying to implement that DFA, the union symbol always confuse me Can ...
otravro's user avatar
0 votes
1 answer
3k views

Construct a DFA accepts set of all strings that begins with 01 and end with 11

I have drawn the DFA for language L1 containing strings starting with 01 and language L2 containing strings ending in 11. For the final DFA, I have concatenated both DFA's. The finals DFA does not ...
Anshika Singh's user avatar
-2 votes
1 answer
2k views

Construct a DFA which accepts all strings containing both 11 and 010 as substrings

I have drawn the DFA for language L1 containing 11 as substring and language L2 containing 010 as substring. But I don't know how to concatenate these two to get the final answer. Please help!
Anshika Singh's user avatar
-3 votes
1 answer
222 views

How can I convert from DFA in to regular grammar?

I have following information. 0 1 -> *q0 q0 q1 q1 q1 q2 q2 q2 q0 I have to convert this in to a regular grammar. I wrote this: ...
grammartest's user avatar

1
3 4
5
6 7
35