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
0
votes
1
answer
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, ...
- 113
1
vote
1
answer
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?
- 55
1
vote
1
answer
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 ...
- 55
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 ...
- 239
2
votes
2
answers
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) ?
...
- 23
0
votes
1
answer
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 ...
- 239
0
votes
1
answer
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 ...
- 279
1
vote
1
answer
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$...
- 239
1
vote
3
answers
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 ...
- 239
0
votes
1
answer
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 ...
- 227
0
votes
2
answers
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!
- 1
-1
votes
1
answer
74
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 ...
- 279
2
votes
1
answer
86
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, ...
- 279
2
votes
1
answer
198
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^*)$ ...
- 279
1
vote
0
answers
19
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, \...
- 279
0
votes
1
answer
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 ...
2
votes
1
answer
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 ...
- 501
0
votes
1
answer
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 ...
- 155
0
votes
2
answers
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 ...
- 155
0
votes
1
answer
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 ...
- 19
1
vote
1
answer
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
2
answers
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 ...
- 11
2
votes
2
answers
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 ...
- 23
0
votes
1
answer
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 ...
- 1
5
votes
3
answers
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
2
answers
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 ...
- 113
1
vote
3
answers
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 ...
- 413
3
votes
2
answers
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,
...
- 215
1
vote
2
answers
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 ...
- 315
1
vote
1
answer
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&...
- 305
3
votes
4
answers
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
...
- 305
-2
votes
1
answer
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 ...
- 305
1
vote
1
answer
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, ...
- 305
2
votes
2
answers
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 ...
- 305
1
vote
1
answer
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 ...
- 315
1
vote
1
answer
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 ...
- 305
0
votes
1
answer
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 ...
- 3
-1
votes
1
answer
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.
- 13
13
votes
4
answers
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. ...
- 257
3
votes
1
answer
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\}$$ ...
- 261
1
vote
1
answer
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$:
<...
- 183
1
vote
1
answer
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....
- 39
1
vote
2
answers
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$, ...
- 155
3
votes
1
answer
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 ...
- 61
1
vote
1
answer
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 ...
- 111
0
votes
1
answer
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 ...
- 17
1
vote
1
answer
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 ...
- 413
-1
votes
1
answer
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 ...
- 121
0
votes
1
answer
57
views
I require assistance in proving this language as not regular
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| <...
0
votes
2
answers
47
views
Difference between this grammar
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 ...
