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.

1,702 questions
Filter by
Sorted by
Tagged with
1 vote
189 views

### Finite State Automata for recognising consecutive characters

I'm currently working on this question as part of some homework, it has me stumped. I'm familiar with finite state automata (FSA), I know how they work and I've read everything I can find on Google, ...
1 vote
3k views

### Language acceptance by DFA

I have some questions regarding acceptance of a language by DFA Whether more that one dfa accept a language Whether a dfa can accept more than one language
1k views

### Proving the language which consists of all strings in some language is the same length as some string in another language is regular

So I've been scratching my head over this problem for a couple of days now. Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose ...
3k views

### Simplification of regular expression and conversion into finite automata

This is a beginners question. I and reading the book "Introduction to Computer Theory" by Daniel Cohen. But I end up with confusion regarding simplification of regular expressions and finite automata. ...
897 views

10k views

### Cost in time of constructing and running an NFA vs DFA for a given regex

Repost from Stack Overflow: I'm going through past exams and keep coming across questions that I can't find an answer for in textbooks or on google, so any help would be much appreciated. The ...
628 views

### Is the set of minimal DFA decidable?

Let $\mathrm{MIN}_{\mathrm{DFA}}$ collection of all the codings of DFAs such that they are minimal regarding their states number. I mean if $\langle A \rangle \in \mathrm{MIN}_{\mathrm{DFA}}$ then for ...
616 views

### Counting with constant space bounded TMs

The problem, coming from an interview question, is: You have a stream of incoming numbers in range 0 to 60000 and you have a function which will take a number from that range and return the ...
722 views

### Does this regular expression equal this automata?

I just came across an exercise which is to find a regular expression for the following automata, such that the regular expression and the automata generate the same language. One solution presents ...
889 views

### LTS of this simple FSP

I have this finite-state process with the corresponding labeled transition system: The FSP is: ...
633 views

### Building a finite state transducer

I know it's possible to build a Finite State Transducer for converting numbers from base 2 to base 4 or 8 or other powers of 2 (translating from base N to base N^M is easy). However I've never seen a ...
531 views

### Is the set of codes of Deterministic Finite-State Automata a regular language?

Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
6k views

### How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?

I created a simple regular expression lexer and parser to take a regular expression and generate its parse tree. Creating a non-deterministic finite state automaton from this parse tree is relatively ...
3k views

### Are supersets of non-regular languages also non-regular?

I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid? Since $L_1$ is not regular, there does not exists a finite automata $M_1$ ...
1k views

### Automata that recognizes Kleene closure of permutations of three symbols

This is an automata theory homework question. I need to create DFA that meets the following criteria: Alphabet $\Sigma = \{ a, b, c \}$ Machine accepts empty string and strings of length that is a ...
569 views

### Optimal myopic maze solver

I was fooling around with Google Blocky's Maze demo, and remembered the old rule that if you want to solve a maze, just keep your left hand to the wall. This works for any simple-connected maze and ...
312 views

### construct regular expression

I need help with the following exercise: Construct an $\varepsilon$-NFA for the following regular expression $(a|\varepsilon)(ba)^*(c^*a|bc)^*$. i already tried this exercise with nerode but i didnt ...
201k views

### How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
9k views

3k views

### Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
1 vote
552 views

2k views

### Words that have the same right- and left-associative product

I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting: Give a non deterministic finite automaton accepting ...
1k views

### How to convert an NFA with overlapping cycles into a regular expression?

If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as ...
7k views

### A DFA for recognizing comments

The following DFA is a lexical analyzer which is supposed to recognize comments. The lexical analyzer will ignore the comment and goes back to the state one. I'm told that there's something wrong with ...
443 views

### Is this language defined using twin primes regular?

Let $\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$ Is $L$ regular? This question looked suspicious at the first glance and I've realized that it is connected with the ...
Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$: $$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$ Which sets of integers can be the length set of a regular language?...