# 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,374 questions
Filter by
Sorted by
Tagged with
12 views

### Sufficient condition for $xy^*z \subseteq L$ for a DFA with $n$ states

In chapter 2 of the New Turing Omnibus, the author considers an unknown finite automata with 6 states. Through trial and error, it is deduced that the words 0101, 0100101, 0100100101 are accepted. It ...
18 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 ...
20 views

29 views

### Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states

Let $L$ be a language, and consider the following relation $\equiv_L$ on strings: $s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$. This is ...
84 views

### Clarification on an Hopcroft book DFA minimization example

At page 156 there is an example on how to find the distinguishable states for the following automaton: The following table shows the distinguishable states: By applying the given definition for ...
186 views

### Check if a NFA accepts a string of non-prime length

Given a nondeterministic finite automaton $A$, give an algorithm that checks whether the language $L(A)$ decided by $A$ contains a string whose length is a composite (i.e. not prime) number. My ...
54 views

### What language does this deterministic finite automaton accept?

Been mulling over this one for hours, my initial thought was { w ε {a,b}* | w is empty, or ends with either ab or ba} but that's clearly wrong as neither aba nor bab are accepted by the automaton. If ...
63 views

### Extracting regex submatch boundaries without backtracking

I'm attempting to develop from scratch a simple regex engine. I would like for my engine to have the ability to report, "The regex matched on a substring of this line starting at index and ...
170 views

### Show $L =$ { w $\in (a,b) ^*$| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular

I try to show that this language is regular: $L =$ { w $\in \ (a,b) ^ *$| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ If I build a NFA and run on it every substring of w (skip other letters ...
121 views

### Is it possible to construct a finite state automata for a decimal adder?

Suppose the strings are of the form x#y#z , where x,y,z are strings formed from the alphabet $\Sigma=(0,1,2,3,4,5,6,7,8,9)$ . The language is accepted if x+y=z is satisfied, for example : 56#65#121 is ...
50 views

### running RAM on a given input

I understand how RAM commands work but I am unable to understand how we use a given input string and find the output. For instance, there's a Random Access Machine which has an input {0,1}*. The ...
44 views

### For an NFA, can we always find a RAM?

For an NFA, can we always find a RAM, which recognises the same language?
94 views

### building NFA for { a^p; p is a prime number, m is a fixed number and m >p >0 }

$\{a^p; p$ is a prime number, $m$ is a fixed number and $m\geq p \geq 0 \}$ I know this is regular since it is finite, but I don't understand how to build an NFA for this if we do not know what $m$ ...
61 views

### Proof that $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states

How can you prove that any DFA accepting the language generated by the regular expression $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states? I first attempted induction on $n$. But I don't ...
150 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 ...
31 views

### Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?

I have question where it asks: Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2? Here's what I've done, but I do reach a contradiction... u=a^r v=a^s x=a^t b^N a^...
63 views

### Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?

For example, a valid number would be 6165156 and an invalid number would be 1566515. I have tried many times to construct a finite state machine for this with no success, which leads me to believe the ...
239 views

### Is checking if regular languages are equivalent decidable? [duplicate]

Is this problem algorithmically decidable? L1 and L2 are both regular languages with alphabet $\Sigma$. Does L1 = L2? I think that it is decidable because you can write regular expressions for each ...
52 views

### Is it necessary for a Push down Automaton (PDA) to have a stack?

I am given a Finite Automaton and the question is to design an Equivalent PDA for it. This is my FA: Is this PDA correct or do I need to add a stack to it? If its right when is the stack needed?
48 views

### How to define enumeration of the set of finite state machines?

I want to write a function that takes N (maximum number of states) as a parameter, enumerates all possible finite state machines up to N states, and returns random FSM with a probability in proportion ...
67 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 ...
39 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$-...
37 views

39 views

114 views

### Finding the upper bound of states in Minimal Deterministic Finite Automata

I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $L(A_1) \backslash L(A_2)$, where $A_1$ is a Deterministic Finite ...
52 views

### Does the order of ripping off the states matter?

Do we get same regular expressions at the end regardless of the order that we take the states step by step? Can somebody prove by exemplification?