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
165 views

### DFA and NFA with 2 Substrings

I am preparing for my CS exam and found this question in a collection of old exams: Find a DFA and NFA with Σ = {o,p,q} that checks if the substrings op and pq are present in the string. I thought, ...
1 vote
60 views

### substitution of same variable in context-free grammars

Above is a theorem coming from the book "Formal languages and automata" by Peter Linz concerning substitution of variables. Could someone explain why A and B have to be different variables?
1 vote
112 views

### variable repetitions in pumping lemma for context-free languages

Above is the proof of the pumping lemma for context-free languages, coming from the book 'Formal Languages and automata' by Peter Linz. The picture below is in support of the proof. I do not ...
2k views

### Why is { w | |w| mod 3 = #_a(w) mod 3 } a Regular Language?

Why is $L=\{w \mid ~|w|\bmod3=\#_a(w)\bmod3\}$ a regular language? $\#_a(w)$ is the number of $a$'s in $w$. So far every language that I saw containing modulo was a ...
133 views

### in 2DPDA and 3DPDA:2 and 3 is the number of tapes or of stacks?

I'm struggling with the definitions of the push-down automata. In 2-DPDA and 3-DPDA, what do the numbers 2 and 3 stand for: for the number of stacks or of read-only tapes (and hence RO heads) ? ...
98 views

### If two states of a DFA are k-equivalent and k+1 equivalent

Consider a DFA $A$ and $k\geq 0$. For states $q$ and $p$ of $A$, we say that $p\equiv_k q$ when $p$ and $q$ agree on all words of length at most $k$; that is, $p\equiv_k q$ when for all words $w$ of ...
69 views

### Prove or disprove that $\{xc o(x) :x \in A\}$ is context-free, where A is a regular language

Suppose o is a map on strings to strings. For every language R, we let $o(R) := \{o(x) : x \in R\}$. If o(R) is a regular language for every regular language R, then prove or disprove that the ...
1 vote
58 views

### If $L$ is regular then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\}$ is regular

Prove/disprove the following claim: If $L\in RL$ then $\{x~|~\exists y ~~s.t~~ xyx^R \in L\} \in RL$ I think that this is true, and my intuition is by using $L_{pq}$ s.t: For every $(p,q)\in Q\times Q$...
1 vote
1k views

### How to prove that $half(L)=\{x|xy\in L,|x|=|y|\}$ is Regular Language

Let $L$ be a regular language. Define: $half(L)=\{x|xy\in L,|x|=|y|\}$ Prove that $half(L)$ is regular as well. I have seen a hard proof by using the DFA A of L, building a NFA B (such that every ...
42 views

### Representing Determinstic Infinite Automata

Does there exist a general approach in mainstream academia for representing a deterministic infinite automata? Unlike the finite kind, this one with infinite number of states. Although there is ...
100 views

### CFL with regular substitution to make a regular language

If I have a CFL, can I define a regular substitution to make it a RL? For example, if I have the language $\{a^nb^n \mid n\ge0\}:$ Define $h(a)=a$ , $h(b)=b$, then $h(L)={a^*}$ , am I right? Thanks!
74 views

101 views

### How would I design a State Diagram (FSM) for a AC unit?

Ok so I'm learning Finite Automata in my Theory of Computation course and understand the basic FSM but can't wrap my head around this question: The AC should only turn on if a person is detected in ...
308 views

### Why 2- way DFA is equivalent to NFA (and thus DFA)?

We know that A read-only Turing machine or Two-way deterministic finite-state automaton (2DFA)is class of models of computability that behave like a standard Turing machine and can move in both ...
74 views

### Checking my Pushdown automaton for $L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$

Could someone please help me check if my automaton is correctly designed? $$L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$$ This was an exercise from our workbook, but their solution is a ...
120 views

### Design a CFG for $L=\{ w \in \{ 0,1 \}^* \}$, where $w$ contains at least three ones

$L=\{ w \in \{ 0,1 \} \}$ where $w$ contains at least three ones Here is one solution for the productions: $S \to A1A1A1A$ $A \to 1A | 0A | \epsilon$ However, now I have a question. Could I modify the ...
301 views

### Sets of problems in different models of computation and cardinality

In university, I was taught the computational model hierarchy given in the following figure: https://devopedia.org/images/article/210/7090.1571152901.jpg Essentially, Pushdown Automata (PDA) can solve ...
1 vote
100 views

### How to convert AFA to ε-NFA / NFA / DFA?

Alternating Finite Automata is a superset of NFA while being equal in expressive power to NFAs. It is defined by 6-tuple (Q∃, Q∀, Σ, δ, Q0, F) where all outgoing transitions from Q∃ are 'or'ed and ...
1 vote
146 views

### Since there is no such thing as infinite memory, can we say that all pushdown automata and Turing machines are actually very big DFA?

If we can make memory infinite, why don't we just give Deterministic Finite Automata an infinite amount of states? Why is it useful to define Turing machines and pushdown automata? Bonus question: Can ...
81 views

### Is the problem of "DFA-TM-INCLUSION" recursively enumerable?

Consider the following problem: Input: A Turing Machine M and a DFA D. Question: Is $L(D) \subseteq L(M)$? Of course, this problem is not decidable. Because it is known that judging whether a word ...
32 views

### A language that is either fully accepted by synchronised DFAs or not at all

I am trying to understand the concept of synchronised DFAs. I have a question where all the states in the DFA after reading that particular word from the alphabet will reach a particular state with ...
173 views

### If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$

For a language $\mathcal{L}$ over an alphabet $\Sigma$, define $$\mathcal{SW(L)} := \{ y ∈ Σ^∗ \mid \exists x \in Σ^* \text{ such that } xyx \in \mathcal{L}\}$$ How can I prove that if $\mathcal{L}$ ...
1 vote
374 views

### NFA to recognize the language ${ab}$

In Michael Sipser's Introduction to the Theory of Computation, Example 1.56 shows how to convert $\left(\text{ab }\cup\text{ a}\right)^*$ to an NFA. It builds up from the smallest subexpression to ...
1 vote
551 views

### Finding a DFA for concatenation

Consider a deterministic finite automaton $M(k) = (Q, Σ, \delta, 0, F)$, with $k ≥ 2$ and $Q = \{0,1,...,k-1\}$ $Σ = \{0,1\}$ $\delta(q,a) = (q+a) \space mod \space k$ $F = \{0\}$ If $L$ is the ...
1k views

### Determining if an NFA accepts an infinite language in polynomial time

Can we determine in polynomial time if the language accepted by an NFA is infinite? The case of DFA is simple, but converting an NFA to a DFA may take exponential time. Also, I ran into this post, ...
1 vote
247 views

### Complement of DFA always give the language which is complemented?

Case:1 Suppose l have one DFA which accepts the set of all strings over {a, b} which starts with aand it's complement is not ...
1 vote
1k views

### Why L1 := { a^n b^m | m, n ≥ 0 and m ≥ n } is regular and L2 := { a ^ n b ^ n | n>= 0 } not regular?

I understand why L2 is not a regular language. We can use the pumping lemma to prove it In the case of L2: assume n = 1 and string = ab We assume that L2 is regular, so it has "pumping length&...
3k views

### What exactly is pumping length in pumping lemma?

Pumping Lemma : For any regular language $\mathbb{L}$, there exists an integer $n$, such that for all $x\in \mathbb{L}$ with $|x|\geq n$, there exists $u, v, w \in \Sigma^*$, such that $x = uvw$, and ...
63 views

### How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?

Let's say that we want to convert the regular expression: (ab + a)* to Finite Automata, where '+' is union and '*' is kleene star. Using the Thompson method, Thompson Method I end up with this: My ...
1 vote
262 views

### Converting Regular Expression to Finite Automata

I am studying "Theory of Computation" by Michael Sipser. I am studying the section where he teaches how to convert "RE to FA". He uses empty transitions for union, concat and star, ...
131 views

### Is ε a part of alphabet or property of alphabet and NFA in FA

I am reading chapter 1 of Michael Sipser's "Theory of Computation" and in the section "Formation defination of NFA" he says the following: 3rd point of the above image is the ...
1 vote
137 views

### Why DFA's configuration space is finite and PDA configuration space is infinite?

I read from this post the term configuration space. I don't know the meaning of configuration space. What is the exactly meaning of configuration space? And why DFA's configuration space is finite ...
1 vote
168 views

### Converting Deterministic Finite Automata to Regular Expression

I am reading Michael Sipser's "Theory of Computation". In one of the proofs he talks about converting "DFA to Regular Expression" and he talks about "GNFAs". I understand ...
57 views

### DFA for the language of non-empty words that are no longer than $2^6$

I was given a question in Automata that I need to prove or disprove, and I thought about this language: $$L = \{w\in \{0, 1\}^*\mid 1\le |w| \le 2^6\}$$ Can you please help me to figure out if its ...
287 views

### DFA without the substring "abb"

$$L_{1}:=\left\{w \in\{a, b\}^{*} \mid w\right. does \ not \ have \ the \ substring \left.a b b\right\}$$ Hello, I wanted to ask whether this dfa is correct according to L1.
3k views

### Proving Equivalence of Two Regular Expressions

Consider the regular expressions $(1+01)^*(0+\epsilon)$ $(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$, where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. ...
43 views

### Build an automaton from a given automaton to prove regularity of more complex strings

let $L$ be a regular language, and let $A=\{\Sigma, Q, q_0, F, \delta\}$ be a DFA such that $L = L(A)$. I need to prove that $$L_p=\{xy\in\Sigma^*\mid\delta(q_0, y)=p\text{ and } \delta(p, x)\in F\}$$ ...
1 vote
99 views

### Use NFA to express the left quotient of the language of a DFA with respect to the language of another DFA

Let $\Sigma = \{a,b\}$, $L_1,L_2\subseteq \Sigma^*.$ $L_1 \triangleleft L_2 = \{w\in \Sigma^* \mid \exists v\in L_1, vw \in L_2\}$ For clarity, here is python code that shows $L_3 \triangleleft L_4$: <...
1 vote
107 views

### Minimal DFA produced by equivalent theorem vs Myhill nerode theorem are different. What is happening?

The problem is-: Site 1 solves this in this way-: https://onlinesmarttrainer.blogspot.com/2020/08/minimization-of-dfa-solved-example.html Site 2 solves this in different way-: https://aswaddev.github....
1 vote
2k views

### Regular expression for all strings not containing $aba$

This is my first post here. We are currently studying regular expressions, and I have been tasked to write a regular expression for the language of all words which do not contain the substring $aba$, ...
434 views

### Proof that a minimal DFA for a finite language has exactly one trap state

Suppose $L$ is a language with a finite number of strings. We know that $L$ is regular. If $M$ is the minimal DFA for $L$, prove that $L$ has exactly one state that we can't exit if we enter it. I ...
1 vote
53 views

### Prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma

I'm currently trying to prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma My proof: If we choose $w$ such that $w=a^P b^P$, then since $|xy| \leq p$, $y$ must be $a^P$, meaning it ...
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
213 views

### Showing that for every NFA with n states, there is a regular expression of length $O(2^n)$

Consider the idea of an extended non-deterministic automation, where transitions can be labelled by regular expressions and not simply by symbols of the input alphabet or $\epsilon$. Such an automaton ...
61 views

### If language $P$ is not regular, is $\{ w \in \Sigma ^* : |w| \geq 1000 \}\cup P$ regular necessarily?

Prove or refute. Let $L = \{ w \in \Sigma ^* :\ |w| \geq 1000 \}$. Let $P$ be a non-regular language. Then $L \cup P$ is regular necessarily. I think it is true, but I don't have any idea ...
I'm trying to prove that L = {$0^n1^m0^n | m,n >= 1$} in NOT regular but I am struggling with the demostration process. I know the conditions are that: $|y| > 0$; $'y'$ can't be empty \$|xy| <...
I was reading a book and there is a part in which they use this grammar $$X \rightarrow xY$$ $$Y \rightarrow yZ$$ $$Z \rightarrow z$$ $$Z \rightarrow \lambda$$ and other times they use this ...