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,533 questions
Filter by
Sorted by
Tagged with
24 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 ...
40 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 ...
35 views

Prove that the language such that the concatenation of any string with its complement is accepted by a regular language is regular [duplicate]

I’m trying to solve the following question: Suppose you have a regular language L with the alphabet {0,1}*. Show the language L’ = {x : x x_c \in L} is also regular. x_c is the flipped version of x ...
77 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 ...
26 views

DFA and RE find out the language. Please can you explain?

Find the regular expression describing following languages over alphabet {0, 1}*. ...
196 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!
32 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 ...
315 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. ...
117 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? ...
94 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 ...
46 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 ...
64 views

Regular language closed under homomorphism

I am trying to solve problems from the textbook 'Introduction to the Theory of Computation' by Micheal Sisper, 3rd edition. I am attempting to show various properties of regular languages and their ...
57 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 ...
42 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 ...
36 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, ...
70 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 ...
128 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 ...
13 views

Cannot figure out what I am doing wrong with Mealy to Moore conversion

I've spent a lot of time on this and still cannot see what I am doing wrong, will appreciate any help. Below the source Mealy machine: According to the solution, there should be two 1s in the ...
99 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 ...
59 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.
251 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 ...
27 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 ...
31 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 ...
39 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 ...
51 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?
25 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 ...
868 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 ...
331 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!
73 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: ...
41 views

How can I convert a Grammar to NFA?

Hello I have a task where I´m stucking at. I have to convert a Grammar to NFA. I have these information: G=(V,T,P,S) V={S}, T{0} and S -> 0S S -> 0 I can´t ...
415 views

If regex describes FSAs, what string formats describe Turing machines?

(Topic summary under the line.) Regex, at least the formal definition featuring only | and *, is used to describe words accepted by a given FSA, but it can be transformed into the corresponding state ...
82 views

How to prove the same states are repeating in Synchronizable DFA?

I'm trying to prove the if $𝑀$ is a $𝑘$-state synchronizable DFA, then it has a synchronizing sequence of length at most $𝑘^3$. first I have to prove that if a string syncs two states, then its ...
169 views

How to describe the language of an automaton in plain English?

How do I describe the following automaton in plain English? The only thing that I can think about when explaining in plain English would be the states, alphabet, start, accepting state, but I think ...
57 views

Efficient algorithm to find a rejecting input of an NFA

I cannot think of a PTIME algorithm to find a rejecting input of an NFA. While it is possible to efficiently find a rejecting input for a DFA, converting an NFA to DFA is too expensive. The algorithm ...
43 views

Question about an answer related to designing an ASM for a sequence detector

The question says: Design a sequence detector that searches for a series of binary inputs to satisfy the pattern 01[0*]1, where [0*] is any number of consecutive zeroes. The output (Z) should become ...
83 views

Prove the language $\{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$ for regular language $L$ is regular

Let $\Sigma=\{0,1\}$ and $L$ be a regular language. Prove that $$Z(L) = \{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$$ is a regular language. I tried to build a NFA based on the DFA that ...
80 views

Drawing transition diagram from transition table

I have a DFA transition table like \begin{array}{cc|c|c} & & 0 & 1 \\ \hline \to & p & qs & q \\ * & q ...
354 views

How is CLR(1) grammar more powerful than LALR(1) grammar

I am unable to understand how Canonical LR(1) grammar is more powerful than LookAhead LR(1). Both have lookahead symbols in their items and works almost similarly, so how can CLR(1) derive a larger ...
54 views

Finding the language generated by this grammar

I'm having problems with this. Can someone help me please. Find the language generated by this grammar over the alphabet $\{0,1\}$: $S\rightarrow BAB\mid CAB$ $BA \rightarrow BC$ $CA \rightarrow AAC$ ...
232 views

How to draw Turing machine for multiplying a number by 2 in base 10

I'm trying to design a turing machine that given a number in base 10 multiplies it by 2. The problem seems trivial if the number is represented in binary so what I've thought is try to convert it from ...
150 views

Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less

I am trying to prove that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ such that a DFA accepting $A_k$ has $k$ states but no less. I thought about proving this in two ways: ...
119 views

NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?

I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are ...
92 views

NFA designing for strings starting with $01$

The question was asked Construct an NFA with set of all strings that start with $10$. The solution provided to me is But my question is what if the automaton receives an input $0$ at the starting? ...
27 views

Possibility of using loops instead of traps

Draw DFA for the language of all strings starting with $a$ and ending with $b$. Now what I have done is Here I used q3 as a trap. But could I do this instead? I have not used trap in the 2nd ...
48 views

Is it possible to create a NFA that accepts only n*"a" or n*"b" inputs?

I'd like to create a NFA that accepts only inputs like "aaaaa";"a";"bb";"bbb", but not like "aab";"aabaa". Is the even possible? As far as I ...
89 views

Maximal minimal DFA for some language of n-bit strings

Notation: $M$ is a DFA; $L(M)$ is the language accepted by $M$; $\min(M)$ is the minimal automaton equivalent to $M$ derived from a minimization algorithm such as the Hopcroft algorithm; and $|M|$ is ...
24 views

How NFA decides how to break up a string?

If we have a language K, that word w=uv, accepts. $K= \{{w \in \{a, b ,c\}^*: \ \vert u \vert_a \ \text{is not divisible by 3}}\}$. Can we land strings like aaaa ...
61 views

Prove language is not Turing-recognizable using contradiction

Show that the language L = {<M>| M is a TM and does not accept <M>} is not Turing-recognizable. Note: Prove by contradiction. No need for reduction. This is the problem I am trying to ...