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
1 vote
1 answer
38 views

Finite State Machine without recursion

I have found utility in state machines that do not have the complexity of recursion: no self or ancestral transitions. Is there a name for this sub-category of FSMs? Are they commonly used or ...
0 votes
1 answer
67 views

Simple description of the LR(0) table generator algorithm?

I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think &...
1 vote
1 answer
138 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 ...
1 vote
2 answers
71 views

Is my regular expression and finite automata diagram for this state table correct?

So i have some theory of computer science homework and I'm struggling with this question currently. I am given the following automaton: $Q = \{q_0,q_1\}$. $\Sigma = \{a,b\}$. $q_0 = q_0$. $F = \{q_0\}...
0 votes
0 answers
16 views

Theory of computation

I am trying to look answer for this question of toc please help me find the answer. The question is : Construct epsilon NFA(Non deterministic finite automata) for regular expression (0+1)*1(0+1)
0 votes
2 answers
2k views

In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the ...
0 votes
1 answer
219 views

Conversion of epsilon NFA to DFA, handling epsilon transitions

I am reading Michael Sipser's "Introduction to theory of computation" 3rd edition, page 55 - 56, the topic "equivalence of DFAs and NFAs" Case 0: Michael Sipser asks us to handle ...
0 votes
1 answer
73 views

How to build a DFA that recognizes a language

I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Build a ...
1 vote
1 answer
190 views

Pumping Lemma $A = \{0^n1^n \mid n \geq0\}$. Prove $A$ is not regular

Question : Are my Justifications Correct? Pumping Lemma $A = \{0^n1^n \mid n \geq 0\}$. Prove $A$ is not regular : Suppose $S = 0^p1^p$ and $p = 3$. Therefore, $S = 000111$. Breaking $S$ into $xyz$ ...
0 votes
1 answer
19 views

Equivalence of echo state networks and DFAs/NFAs

Echo state networks are theoretically equivalent to DFAs/NFAs, but how would you use an ESN to parse a regular language? Would you just feed many different input strings, some from the language and ...
5 votes
2 answers
315 views

Creating a deterministic finite automaton for strings of 2k ones and 3q zeros or a general language

I was requested to draw the graph of a finite state machine whose language is $$L = \{ w \in \{0, 1\}: w \text{ has $2k$ ones and $3q$ zeros }\}$$ In other words, the number of ones must be even and ...
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, ...
0 votes
1 answer
112 views

Copy operation in under 9 states?

There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following ...
0 votes
0 answers
13 views

Right-regular grammar conversion to NFA: production rule with only one variable on right side

I'm trying to convert a right regular grammar to an NFA. I understand that I need to create a state for every variable and add transitions according to the production rules. But what if there is a ...
1 vote
1 answer
36 views

Counting States in the trim automaton for $\cup_{i=1}^{p} L_i \circ L'_i$

Preliminaries. Let $n,m,i,j,p,c \in \mathbb{N}$ with $n,m,i,j,p,c \geq 1$. Let our alphabet be $\{0,1\}$, with non-empty languages $ L_i \subseteq \Sigma^n$ and $ L'_i \subseteq \Sigma^m$. The other ...
2 votes
1 answer
62 views

Does my finite state automaton accept a string iff it contains the given string as a substring?

I am trying to write down the generalized form of the finite automata which accept strings which contain as a substring an arbitrary string. Here is what I have come up with — I was hoping someone ...
0 votes
0 answers
22 views

ALL-NFA is PSPACE-complete

Show that $ALL-NFA$ = {$\langle M\rangle : M$ is $NFA$ and $L(M) = \Sigma^*$} is $PSPACE-complete$. I've manged o prove that it is $PSPACE$. It is easy to see that $\overline{ALL-NFA}\in NPSPACE$ (TM ...
2 votes
2 answers
4k views

Exactly what is the difference between Finite Automata and Transition Graphs?

I haven't found a good enough answer by googling. Here's what i know: TG's can have more than one initial state In TG's, Edges/transitions can be labelled with strings In TG's, it is not necessary to ...
0 votes
0 answers
21 views

Complexity of checking equivalence of finite automata [duplicate]

Given two finite automata $M_1,M_2$. I couldn't find the computational complexity of the problem of determining whether $L(M_1) = L(M_2)$.
0 votes
1 answer
24 views

Counting States in the trim automaton for $(L_1 \cup L_2 \cup \ldots \cup L_p) \circ L'$

Preliminaries. Let $n,m,p \in \mathbb{N}$ with $n,m,p > 1$. We allow that $p$ could be large but still bounded by a function of $n$: $p = O(2^n)$. Let our alphabet be $\Sigma = \{0,1\}$, with non-...
2 votes
2 answers
69 views

Counting States in the trim automaton for $L\circ L'$

Preliminaries. Let $n,m \in \mathbb{N}$. Let our alphabet be $\Sigma = \{0,1\}$, with non-empty languages $ L \subseteq \Sigma^n$ and $ L' \subseteq \Sigma^m$. We follow the standard definition for ...
1 vote
2 answers
28 views

Confusion with Execution of NDFA

I do not understand the "execution graph" (I think that's what it's called) of the following Non-Deterministic Finite Automata, given on pg 48-49 of Sipser's Intro to TCS (3rd edition): And ...
0 votes
1 answer
39 views

Simplifying regex expression (L+M*)*

To simplify it, it seems that we can do $(L+M^*)^* = (L+M)^*$, but I also need to prove it.$(L+M)^* ⊆ (L+M^*)^*$ seems straight forward. However, $(L+M^*)^* ⊆ (L+M)^*$ is what I couldn't figure out. ...
1 vote
1 answer
86 views

Product Construction for DFAs with different alphabets

How would you modify the Product Construction for DFAs to find a DFA that recognises the union of two regular languages with different alphabets. I am not looking for a way of finding an NFA then ...
0 votes
0 answers
33 views

Help with converting the DFA to a regular expression using Ardens theorem

Can someone explain to me how to convert this DFA to a regular expression? I have tried using Arden’s theorem but I don’t know how to simplify the equations to get the regular expression for this DFA. ...
-2 votes
1 answer
340 views

Proving that removing unreachable states from $M$ does not change $L(M)$

What is the idea behind proving that: Removing unreachable states from a DFA $M$ does not change $L(M)$. I don't know what cases I need consider. Consider any $w\in \sum^*$ and then check for the ...
0 votes
0 answers
59 views

Proving a certain language is regular by constructing a DFA

Let $L$ be a regular language over the alphabet $\sum$, prove that the language defined by $\hat{L} = \{uv \in \sum^* | u^Rv \in L \}$ is regular. There is guidance in the exercise that instructs us ...
1 vote
2 answers
68 views

Need to create CFG that requires sum of other letters

I have a homework assignment that requires me to create CFG $G$ for $$L = \{a^i b^{i+j+k} c^j d^k\}$$ so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or ...
0 votes
1 answer
55 views

How this state set of DFA was retrieved from the given NFA

I have this NFA: 1,{2, 3} 2,empty 3,{4} 4,empty All the arrows in this NFA are epsilon-arrows. I understand that all possible states that can be reached from each ...
0 votes
1 answer
50 views

Why must 2 distinct strings go to the same state in a DFA?

I'm finding it difficult to understand why due to the pigeonhole principle, 2 distinct words must go to the same state in a DFA. Is it that if there are n words and m states, where there are more ...
3 votes
1 answer
71 views

Brzozowski's algorithm for Kleene star NFA

I have some troubles in understanding of the Brzozowski's algorithm for NFA to minimized DFA transformation. Or maybe I'm doing a mistake in the NFA to DFA transformation steps. The Algorithm, as ...
0 votes
0 answers
11 views

How can I describe an FSA where one or more inputs generate outputs but do not cause transitions?

I have been asked to describe through an FSA a system where some inputs do not determine any state transitions, but that provide outputs. There is no self-transition, and the input is not rejected: ...
0 votes
0 answers
33 views

Desgining NFA under certain constraints

I've got homework to design NFA to accept a set of strings over {a,b,c} in which each string of the language satisfies: "cac" is a substring and "cc" is not a substring and the ...
0 votes
1 answer
1k views

Determine if an NFA accepts infinite language in polynomial time

Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time). For any DFA,...
2 votes
0 answers
197 views

What extension of a finite-state machine is modeled by aliasing inputs?

Recently, I’ve been interested in the console of the Source game engine, more specifically, its alias command, which allows one command to invoke others. It may ...
0 votes
0 answers
26 views

How to prove (L+M)* = M*.(L.M*)*

Question is to simplify (LM*)* and I couldn't figure out a way to simplify it. Since (L+M)* = M*.(L.M*)*, I guess we can say that it cannot be simplified more. So how do we prove that they are the ...
0 votes
1 answer
83 views

Intersection of Infinite Regular Language with CFL

Intersection of any finite regular language with anything( CFL or not CFL) will be finite but what about intersection of infinite regular language with CFL or not CFL. Does the resultant will be ...
1 vote
2 answers
84 views

Prove a language created by applying a function on a regular language is regular

Let $L$ be a language over $\Sigma=$ {$a,b,c$} We define $\forall w\in \Sigma ^{*}$ the function $T$ s.t. $T(w)$ is the word we recieve after removing all instances of $a$ in $w$. Let $T(L)=${$ T(w) : ...
1 vote
1 answer
437 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 ...
2 votes
1 answer
90 views

Regex where all strings containing an even number of 0's:

Question is to construct a regex where all strings containing an even number of 0's: By constructing DFA graphically, it is $$(1^*+01^*0)^* $$ But it is also $$1^*(01^*01^*)^*$$ Can we prove that they ...
0 votes
1 answer
351 views

How to construct an NFA Ai for the given Regular property P1 and P2?

Let AP = {a; b; c}. Consider the following regular safety properties: (a) P1: If a becomes valid, afterwards b stays valid ad infinitum or until c holds. (b) P2: Between two neighbouring occurrences ...
0 votes
1 answer
67 views

Explain meaning of states and transitions for DFA that accepts two binary words (a,b) with b = 5a

I was provided with the solution to the language being represented. An example of accepted input would be [001][101]. The DFA that would recognize this language is below. What do the states represent?...
0 votes
1 answer
65 views

What could be possible NFA for the RegEx "a?"

I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$ I am wondering if I should deconstruct the RegEx as - Concatenation of $a+$, $(b|c?)$ together with $c$ OR ...
1 vote
1 answer
76 views

Constructing a deterministic finite automaton from a particular regular expression

This is the given question- Construct a DFA over the alphabet {0,1} such that it accepts all strings containing even number of 0's OR the number of 1's divisible by 3. The very first problem I've ...
3 votes
3 answers
1k views

DFA that accepts strings whose 10th symbol from the right end is 1

Problem is "Constructing a DFA accepting set of all strings whose 10th symbol from the right end is $1$ over $\{0,1\}$" The NFA is easy $$(0+1)^*1(0+1)^9$$ but DFA has to have minimum $2^{10}...
1 vote
2 answers
86 views

Finite state machine that accepts every word with at least one c, or different value of parity of the counts of a's and c's

few weeks ago I had an exam in automata theory course and I've been asked to write the following non-deterministic finite automata Write a NFA which accepts the following language - the language ...
1 vote
1 answer
78 views

Transform a non-regular language into a regular one using sort

Is there a way where sort turns a non regular language into a regular one. What I mean by sort is this: Consider the language $L =$ { $bac, cbca, acbb$}. $sort(L) = $ {$abc, abcc, abbc$} respectively. ...
3 votes
1 answer
625 views

Can we transfer every DFA to DFAs with start state having no in edge?

The start state cannot have any "in edge" (an arrow point directly to the start state) and only out edge is possible for the start state. Other states except the start state are free of ...
3 votes
3 answers
283 views

PDA for a language where the second part is not the reverse of the first part

I came across an exercise for constructing a PDA for the following language: $$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$ Where $L \subseteq ({a,b,c})^*$ So $n$ and $m$ are both a ...
0 votes
1 answer
54 views

Is there a typo in this excerpt from the book?

Michael Sipser's Introduction to Theory of Computation: Is there a typo in the highlighted line? I ask that because near the beginning it says that R is a set of states of N, and that R itself is a ...

1
2 3 4 5
35