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
1
vote
1
answer
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?
- 47
1
vote
1
answer
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 ...
- 47
3
votes
4
answers
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 ...
- 241
2
votes
2
answers
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) ?
...
- 23
0
votes
0
answers
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 ...
- 241
0
votes
1
answer
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 ...
- 225
1
vote
1
answer
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$...
- 241
1
vote
3
answers
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 ...
- 241
0
votes
1
answer
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 ...
- 157
0
votes
2
answers
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!
- 1
-1
votes
1
answer
64
views
prove $A$ is context-free
Prove that the following language is context-free by giving a context-free grammar that generates the language: $A = \{a \in \{0,1\}^* : \text{ no character in an even position is a 0 or no character ...
- 225
2
votes
1
answer
64
views
Prove that if C is a regular language, then the language $\{x x^R : x\in C\}$ is context-free
Let $C$ be a regular language. Prove that the language $D = \{x x^R : x\in C\}$ is context-free.
It's clearly important that $C$ is regular; if the hypothesis were weakened to C being context-free, ...
- 225
2
votes
1
answer
48
views
prove that context free languages are closed under the $\circ$ operation
Prove that if $C$ and $D$ are context-free languages, then so is $C\circ D := \cup_{n\ge 0} C^n D C^n $.
I know that $\{0^n 1 0^n : n\ge 0\}$ is context free, being the intersection of $L(0^* 10^*)$ ...
- 225
1
vote
0
answers
16
views
an NFA whose corresponding DFA has at least $2^n - \alpha$ reachable states [duplicate]
Is there an NFA with n states so that the DFA resulting from the standard conversion of the NFA to a DFA has at least $2^n - \alpha$ reachable states for some integer $\alpha \ge 1$?
Let $N= (Q, \...
- 225
0
votes
1
answer
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 ...
2
votes
1
answer
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 ...
- 468
0
votes
1
answer
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 ...
- 155
-3
votes
0
answers
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 ...
0
votes
2
answers
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 ...
- 155
0
votes
1
answer
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 ...
- 11
1
vote
1
answer
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
2
answers
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 ...
- 11
2
votes
2
answers
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 ...
- 23
0
votes
1
answer
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 ...
- 1
5
votes
3
answers
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
2
answers
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 ...
- 113
1
vote
3
answers
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 ...
- 369
3
votes
2
answers
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,
...
- 183
1
vote
2
answers
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
1
vote
1
answer
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&...
2
votes
4
answers
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
...
-2
votes
1
answer
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
1
answer
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, ...
2
votes
2
answers
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
1
answer
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
1
vote
1
answer
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 ...
0
votes
1
answer
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 ...
- 3
-1
votes
1
answer
43
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.
- 13
0
votes
0
answers
31
views
Use NFA to express the acceptance of a rule
$\Sigma$ is letter set $\{a, b\}$. for word $w \in \Sigma^{*}$ and 2 language $L_{a}, L_{b} \subseteq \Sigma^{*}$ defined on $\Sigma$, we define language $w\left\{a \mapsto L_{a}, b \mapsto L_{b}\...
- 163
0
votes
0
answers
28
views
Algorithm to remove null transitions from an NFA?
I have an NFA represented as a vector<set<transition> > in C++. (Indices correspond to states, each index keeping a set of all transitions from the ...
- 1
13
votes
4
answers
2k
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. ...
- 233
3
votes
1
answer
39
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\}$$ ...
- 241
1
vote
1
answer
70
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$:
<...
- 163
1
vote
1
answer
47
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....
- 41
1
vote
1
answer
112
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$, ...
- 155
3
votes
1
answer
172
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 ...
- 61
1
vote
1
answer
35
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 ...
- 111
0
votes
0
answers
40
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 ...
- 17
1
vote
1
answer
60
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 ...
- 369
-1
votes
1
answer
59
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 ...
- 121