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.

200 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8 votes
0 answers
152 views

Make a tag system simulate a finite automaton?

Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end ...
foobar's user avatar
  • 181
7 votes
1 answer
253 views

A Turing machine with each cell accessed at most $10$ times has an equivalent NFA

I am confused by the following claim: Let $T$ be a (decider, single-tape) Turing machine with the property that for every input, every cell on its tape is accessed at most $10$ times. Then there is a ...
Emolga's user avatar
  • 171
6 votes
0 answers
308 views

Why does Non Determinism not enhance FA like it does for PDA

Both Deterministic and Non deterministic Finite Automata can recognize the same universe of regular languages. On the other hand, Deterministic Push Down Automata can only recognize a subset of ...
AnkithD's user avatar
  • 161
5 votes
0 answers
94 views

Languages recognized by finite state automata of polynomially growing size

In the course of my research (condensed matter physics stuff), I stumbled over the following concept: The class of regular languages can be defined via finite state machines (FSM): A language $L$ is ...
NcLang's user avatar
  • 91
4 votes
0 answers
76 views

Inverse operation to concatenation for regular languages

I'm currently in need of the inverse operation of the concatenation of 2 regular languages. Formally, for 3 regular languages $A,B,C$ such that $A \cdot B = C$, only $A$ and $C$ are known, and $B$ is ...
Michael Schmidt's user avatar
4 votes
0 answers
112 views

Simultaneous reachability of NFA states

Suppose I have a $n$-state non-deterministic finite automaton $F$ over alphabet $\Sigma$. Let $S(x)$ be the set of states reachable from the starting state by consuming string $x$. I am interested for ...
orlp's user avatar
  • 12.5k
4 votes
0 answers
98 views

Does Brzozowsky's algorithm always produce the right minimum DFA?

Let's say I have this NFA automaton A: ...
Andrea's user avatar
  • 41
4 votes
0 answers
106 views

Quality of Reduction of finite automata using different congruences

I am looking for an example, which corresponds to what I've learned in my Applied Automata Theory Class: Given a NFA $\mathcal{A}$, a $\approx _\mathcal{A}$ quotient automaton can be bigger then a $...
Laura's user avatar
  • 534
3 votes
1 answer
169 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 ...
xdavidliu's user avatar
  • 818
3 votes
0 answers
102 views

Minimal regular expression from minimal NFA for finite language in polynomial time?

Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language? This question is based on a recent question regarding ...
Patrick87's user avatar
  • 12.7k
3 votes
0 answers
51 views

Tree Automata Operators

I am trying to understand the Projection operation (linear tree homomorphism) and Cylindrification operation (inverse tree homomorphism) from the book. Linear Tree homomorphism is defined as follows: ...
GermanShepherd's user avatar
3 votes
0 answers
1k views

NFA random generator

I'm working on a NFA to DFA conversion tool that is different from the Subset Construction and I need to test this tool. In order to be sure that the immplementation has no bug I'd like to generate a ...
Advicer's user avatar
  • 181
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
2 votes
0 answers
62 views

Translating weighted regular expressions with the complement operator to weighted deterministic automata

I want to implement regexp search via translation to deterministic automata, as a toy project. TLDR: how to combine the extended regular expressions with the weighted regular expressions, with the ...
user2373145's user avatar
2 votes
0 answers
73 views

How to build a minimal string matching DFA with limited memory?

I am working on finite state machine pruning, a problem that requires me to build finite state machines (in the manner of the Aho Corasic algorithm) to match an evolving input string against a set of ...
FUZxxl's user avatar
  • 866
2 votes
0 answers
40 views

closure property violated by palindrome language

It is well established that palindrome language is non-regular. The one way to prove it is by means of pumping lemma. The other way is violating the closure properties of regular language. The ...
madeel's user avatar
  • 21
2 votes
0 answers
36 views

Regular string relations - proof of correctness

Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular (rational) relation. We define the obligatory rewrite relation over $T$ as follows: $$ R^{obl}(T) := N(T) \cdot (T \cdot N(T))^* $$ $$ N(T) := ...
Denis Kyashif's user avatar
2 votes
0 answers
263 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 ...
usera's user avatar
  • 21
2 votes
0 answers
88 views

Which of these languages is regular? The Pumping Lemma seems to show none are

I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular? $$ \{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
regular's user avatar
  • 21
2 votes
0 answers
38 views

Why are VFSMs not more commonly used?

For a job several years ago I worked with a team using technologies built around Virtual Finite State Machine models for system fault analysis and remediation. Since then, I've found it to be a ...
Bill's user avatar
  • 121
2 votes
0 answers
120 views

Intersection of two deterministic parity automata

Given two deterministic parity automata $A_1=(Q_1,\Sigma,\delta,q_{01},c_1)$ and $A_2=(Q_2,\Sigma,\delta,q_{02},c_2)$ with the finite set of states $Q_i$, the finite alphabet $\Sigma_i$, the ...
kafka's user avatar
  • 391
2 votes
0 answers
247 views

Extending Thompson's NFA algorithm with backreferences

I'm looking for an algorithm as efficient as possible for a regex engine that supports submatch tracking (a.k.a capturing parentheses) and backreferences. What I mean by as efficient as possible is ...
Celelibi's user avatar
  • 423
2 votes
0 answers
562 views

Number of non deterministic finite automata that can be constructed for $n$ states and alphabet with $m$ symbols

I came across the fact that The number of DFAs that can be constructed for $n$ number of states and alphabet containing $m$ symbols is $n\times (\color{red}{n}^m)^n \times 2^n$ So I was wondering ...
RajS's user avatar
  • 1,607
2 votes
0 answers
78 views

Minimization of simple cyclic automata

Version 1 of the question: I am looking for any correct $O(n)$ algorithm in the literature which will solve the DFA minimization problem referred to in the quote below from [Almeida & Zeitoun 2008]...
ShyPerson's user avatar
  • 911
2 votes
0 answers
198 views

State of the Art in linear-time DFA minimization

What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time? Here’s what I’ve been able to find so far: The acyclic case has been solved. So any ...
ShyPerson's user avatar
  • 911
2 votes
0 answers
336 views

Powerset construction of minimal NFA will result into minimal DFA?

I was just thinking about the powerset construction and it is clear to me that the powerset construction will result into a DFA $D$ with possibly redundant states, as the NFA $N$ is not minimized. But ...
Raldir's user avatar
  • 21
2 votes
0 answers
325 views

What is a regular expression for solutions to the dog/cat/mouse river crossing puzzle?

This is a question that's been bugging me off and on for years, ever since I took a compiler theory class as an undergraduate. There, we learned how to convert a regular expression into a non-...
Daniel Schepler's user avatar
2 votes
0 answers
76 views

How many states in a 2 delay (or n delay) transducer (using DFA)?

An n delay transducer in the context of the problem simply means that the output is same as the input but after waiting for 2 more symbols in the input. 2-delay transducer: We can't show any result ...
aste123's user avatar
  • 445
2 votes
0 answers
73 views

Expressing classic automata in modern terms

This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions (...
Maksim Yegorov's user avatar
2 votes
0 answers
100 views

How does a minimal DFA ensure minimal computational cost?

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence: The minimal DFA ensures minimal computational cost for tasks such as pattern matching. ...
babou's user avatar
  • 19.3k
2 votes
0 answers
117 views

When is the best time to include an ε-transitions in a NFA state diagram?

While doing my NFA homework in my automata class, I feel like I'm not taking advantage of the ε-transitions I'm learning about. I can solve problems without using it. It's not like I really need it, ...
Arrow's user avatar
  • 145
2 votes
1 answer
129 views

Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
Swordow's user avatar
  • 19
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
1 vote
0 answers
30 views

Is there an algorithm for generating non comparable boolean vectors?

First some context: A Boolean Network of $n$ components is a function $f$ from the set $\{0,1\}^n$ (set of vectors of $n$ components whose values are 0 or 1) to itself. The dynamical behavior of a ...
Raúl Astete's user avatar
1 vote
0 answers
50 views

Finite-state transducer to accept $i$'th word of DFA

If I have a DFA $D$ that accepts some regular language $L$, is it possible to construct some finite-state transducer $T$ that takes in an index $i$, and puts out the $i$'th word in $L$, ordered ...
Jake's user avatar
  • 368
1 vote
0 answers
111 views

Design a two-tape deterministic Turing machine M that recognizes the language L3= {x#(0^k) #y : x, y ∈ {0, 1}* , x = y ∧ |x| = k}

I'm having a hard time trying to write a two tape Turing machine I wanted to first think Oh all I'd have to do is scan from left-to-right till I find the strings that matches the accepted strings) ...
Kotha's user avatar
  • 11
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
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
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
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
1 vote
1 answer
137 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 ...
Kacper Ogórek's user avatar
1 vote
0 answers
50 views

What is the connection between finite automata and logic (sequential calculus)?

Languages recognized by finite automata are exactly those definable by sentences of the sequential calculus, and also exactly those definable by rational expressions (also called regular expressions) ...
Oleg Dats's user avatar
  • 299
1 vote
0 answers
35 views

How to prove existance and construct finite-state transducer between two different FSM?

For example I have 2 simple FSM. I will use regular expression for clarity. ...
Oleg Dats's user avatar
  • 299
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\}...
andyiscoding's user avatar
1 vote
0 answers
195 views

How to efficiently flatten a hierarchical state machine?

David Harel's StateCharts introduces hierarchical states and history mechanism, which are really powerful when modeling complex system behaviour. But when doing model based testing we need a "...
kexanie's user avatar
  • 111
1 vote
0 answers
1k views

Draw a CFG (context-free-grammar) that starts and ends with the same symbol yet has odd number of 1's

I figured out that the CFG that starts and ends with the same symbol in alphabet $\Sigma=\{0,1\}$ will be : S -> 0A0|1A1|0|1| A -> 0A|1A|𝜖 How can i interpret the odd number of 1's also?
K11's user avatar
  • 11
1 vote
0 answers
683 views

How design a Deterministic finite automata which accept string starting with 101 and how to draw transition table for it if there is a dead state

I’m trying to design a DFA which accept string starting with 101 if the string start with 0 then it goes to dead state.Is my design is correct or wrong? And I don’t know how to draw transition table ...
Stark's user avatar
  • 11
1 vote
0 answers
54 views

k-limited solution for PCP

So there's following problem, that has been bugging me for the last few days: A solution of a PCP $ i_{1},\dots,i_{n}$ with the cards $(x_{1} ,y_{1}),\dots,(x_{m}, y_{m})$ is considered as $k$-...
Momo's user avatar
  • 35
1 vote
0 answers
41 views

Chomsky hierarchy for finite state transducers

In this question in the first answer someone mentions a "special transduction hierarchy". I cannot find anywhere anything about it. Could someone point me to resources on this topic?
alagris's user avatar
  • 143
1 vote
0 answers
100 views

How to generate a DFA that recognizes a non-regular Grammar

How would you convert the following grammar to a DFA that recognizes its language? \begin{align} &G = (\{S,A,B\},\{0,1\}, S, P)\\ &P\colon &&S\rightarrow A1B\\ &&&A \...
DSN94's user avatar
  • 111