# 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,614 questions
Filter by
Sorted by
Tagged with
1 vote
34 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
72 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 ...
92 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) ? ...
37 views

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

Let $p,q$ be two states of a DFA, such that $p\equiv_kq$ and $p\equiv_{k+1}q$. Does it mean that $p\equiv q$ ? I don't think so, because if the minimization algorithm can continue, they might be ...
47 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
38 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
164 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 ...
24 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 ...
83 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!
64 views

57 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 ...
137 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 ...
58 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 ...
48 views

### What does the concatenation of any number of 01 mean?

I'm trying to construct a DFA. I've tried x = 01 and y = 01 and concatenating them to make 0101 but this did not work. I think I'm confused on what's being asked. Please ignore this question. I've ...
74 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 ...
280 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
62 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
52 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 ...
61 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 ...
29 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 ...
102 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
46 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
377 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 ...
789 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
75 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
47 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&...
257 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 ...
31 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
32 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, ...
88 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
103 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
51 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 ...
53 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 ...
$$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.