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 ...
Synesso's user avatar
  • 113
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)
Amy's user avatar
  • 1
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 ...
lafinur's user avatar
  • 181
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 ...
Grizzly_ed's user avatar
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 ...
ShyPerson's user avatar
  • 911
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 ...
GeoArt's user avatar
  • 1
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 ...
ZarakshR's user avatar
  • 125
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)$.
user1868607's user avatar
  • 2,230
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-...
ShyPerson's user avatar
  • 911
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 ...
ShyPerson's user avatar
  • 911
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 ...
revision's user avatar
0 votes
0 answers
32 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. ...
amanda che's user avatar
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 ...
Yarin's user avatar
  • 129
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: ...
Antonio Esposito's user avatar
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 ...
Ilya Lakhin's user avatar
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 ...
Yarin's user avatar
  • 129
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 ...
steatoda's user avatar
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 ...
Abced Decba's user avatar
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. ...
steatoda's user avatar
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) : ...
Aishgadol's user avatar
  • 316
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 ...
steatoda's user avatar
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 ...
Sefa Kalkan's user avatar
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}...
steatoda's user avatar
1 vote
2 answers
85 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 ...
eeee25's user avatar
  • 11
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 ...
Pouya Kafashi's user avatar
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. ...
Anonymous's user avatar
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 ...
Sbeve's user avatar
  • 41
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 ...
MrKhonsu's user avatar
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 ...
43674652439's user avatar
-4 votes
1 answer
68 views

Describe the language accepted by the DFA

Describe the language accepted by the DFA shown above
GooglyMaster's user avatar
0 votes
1 answer
53 views

Is pumping lemma not applicable for every 'long enough' string in the language?

I recently learnt that a subset of a regular set may not be regular. This is causing me confusion as I imagined if a set is regular then every string longer than $p$ can be pumped in the language. So ...
Axo's user avatar
  • 115
1 vote
1 answer
76 views

What are non-isomorphic NFAs

I came across the following problem while doing my Formal Language class assignment and hope someone can give me some hints: I have $\Sigma = \{0,1\}$ and $L=\{x0a \mid x \in \Sigma^*, a \in \Sigma\}$...
x_Xbd's user avatar
  • 15
0 votes
1 answer
47 views

Algorithm to determine the regularity of a language

According to the answer provided by Janoma, there are several methods to determine the regularity of a language. Theorem Let L ⊆ Σ∗. The following conditions are equivalent: L is generated by a ...
Alan Whitteaker's user avatar
0 votes
2 answers
107 views

Can a DFA have multiple of the same state?

I need to create a DFA for a sequential order of states e.g. A -> B -> C -> B -> A and so on, where 'A' is the start and finish state, 1 is a transition to the next state and 0 just loops ...
needhelpwiththisQ's user avatar
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?...
Patrick's user avatar
  • 11
1 vote
1 answer
306 views

Getting an NFA with only one initial and final state without epsilon transitions

Given an NFA with more than one initial or final state, it is possible to convert it to another NFA with only one initial or final state by using epsilon transitions. To remove the epsilon transitions,...
ricardorr's user avatar
  • 115
0 votes
1 answer
32 views

Designing DFA for a language

I am working on designing a DFA with the language $a^i b^j c^k$ such that $i + j + k$ is odd I thought along the following lines: $i+j+k$ is odd $\Rightarrow$ two of them are even and one is odd or ...
nicku's user avatar
  • 143
1 vote
1 answer
106 views

How to design a DFA that accepts the language of pairs of binary words (a,b) with 5a=b?

Let $\begin{bmatrix}0\\ 0\end{bmatrix}$ be a two-column vector with $0$ in the first row and $0$ in the second row. Let $\Sigma_2 = \left\{ \begin{bmatrix}0\\ 0\end{bmatrix}, \begin{bmatrix}0\\ 1\end{...
Patrick's user avatar
  • 11
0 votes
0 answers
39 views

prove that Every DPDA has an equivalent DPDA that always reads the entire input string

I am reading Michael Sipser's book Introduction to the Theory of Computation and in the section 2.4(chapter 2 and DCFLs section) there is a proof for the lemma that says "Every DPDA has an ...
emdhdr's user avatar
  • 1
1 vote
1 answer
132 views

What is the smallest NFA you can design for {a^n : n =/= 1003}

What is the smallest NFA that could be design for a^n where n!=1003? I have been racking my brain at this for a while but still can't reduce the number of states required from 1004. Here state(1003) ...
staz6's user avatar
  • 25
0 votes
0 answers
35 views

Is there any way to tell which states are final states in a finite state automata given only its grammar?

Problem In the problem, I was given the grammar for a non-deterministic finite state automata (NDFSA). There was no other useful context given. The problem asks you to use this grammar to draw the ...
Brett Smith's user avatar
-4 votes
2 answers
80 views

A string that contains aabb, does this work?

Can you verify this like please bro please tell me the answer to my question
Don Dang's user avatar
3 votes
1 answer
69 views

Building the minimal automaton from the syntactic monoid of a language

I'm studying the algebraic view of automata theory. One of the basic results is that the syntactic monoid of a language $L$ is the transition monoid $M(A)$ of the minimal automaton $A(L)$ accepting $L$...
gigabytes's user avatar
  • 448
0 votes
0 answers
28 views

Meaning of term $L(\bar{n})$

I was studying a few terms on finite automatas, and came across the following terms: $L(\bar{n})$ and $\overline{L(n)}$ The latter term stands for complement of a given NFA, but what does $L(\bar{n})$ ...
h4kr's user avatar
  • 115
0 votes
2 answers
119 views

Every DFA accepting a finite language must contain a dead state?

I came a across a question where there were some statements made on Finite Automata, DFA and their states. One such statements in the question was that a "Every DFA accepting a finite language ...
h4kr's user avatar
  • 115
0 votes
0 answers
52 views

How does the regular expression '^(a+)+$' lead to this specific NFA?

OWAPS has an article on ReDoS (archived). In it, they use the regular expression ^(a+)+$ as an example for ReDoS vulnerabilities. They provide this illustration of ...
Alex Povel's user avatar
-1 votes
1 answer
38 views

find the minimization of the dfa

so this is the question , I have to minimize this DFA this is How I did it but when I checked for answers , this is what it was, can someone please explain to me what mistake I made? I have been ...
gratus richard's user avatar
0 votes
0 answers
24 views

In Pumpin Lemma, let's say we have a decomposition of the string s = xyz, is it necessary for x to take the automaton through distinct states?

I understand what Pumping Lemma is, how it works and also understand it's proof. The gist is that it uses "Pigeon Hole" principle to guarentee us a repeatation in the sequence of states and ...
Pratik Hadawale's user avatar
0 votes
1 answer
42 views

Does every regular expression describe only 1 language?

If we have a regular expression $R$, will $R$ describe only regular language $L$, but that language $L$ can have multiple different regular expressions such as $Q,W,A,S,D \ etc..$ describing it Also, $...
Pratik Hadawale's user avatar
-1 votes
3 answers
52 views

Is it possible to divide a string, according to pumping lemma, from a language in a way that pumping a section would render the language -non regular

I understand that pumping lemma can only be used to prove that a certain language is "non-regular", it cannot be used for proving regularity But since, it's a property of regular language, ...
Pratik Hadawale's user avatar

1
2 3 4 5
34