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,626
questions
0
votes
0
answers
22
views
Is my DFA optimal?
I designed this FSM graph to demonstrate a DFA that would accept any string that
is of length 5,
must contain a d,
can only have as and/or bs before the d, and
can only have bs and/or cs after the d.
...
- 101
1
vote
0
answers
9
views
What is region construction in timed automata?
I've recently started self-learning timed automata.
There's this theorem in there that a timed automaton can be converted to a DFA using a "region" construction. I've looked up references on ...
- 111
0
votes
1
answer
33
views
Does this DFA prove closure under Perfect Shuffle?
I'm self studying Introduction to Theory of computation and I'm a bit confused about a problem definition. I'm trying to understand and verify whether my proof is correct or not.
Question: Prove that ...
- 103
-1
votes
0
answers
18
views
Language for the the set of strings with no more than two consecutive a’s [duplicate]
I need to define a basic language for the set of strings with no more than two consecutive $a$’s over $\Sigma = \{a,b\}$.
Does this look correct?
$L = (\{b\} \cup \{ab\})^* \cup ((\{b\} \cup \{ab\})^* ...
- 1
1
vote
2
answers
42
views
does finite automate have memory?
I've learned that finite automata doesn't have memory and hence languages, where there are comparison within the string, can't be considered regular.
In our university there was a question where the ...
- 11
0
votes
0
answers
20
views
Is there some way to make JFLAP display the 5-tuple for the current DFA?
I am using JFLAP in my class and would like to produce the 5-tuple M={Q,Sigma, delta, q0, F} from the DFA I just created. Drawing a DFA from the 5-tuple would also be nice.
2
votes
1
answer
69
views
minimal DFA transition function clearification
Statement:
Given any dfa $M$, application of the procedure 'reduce' (see below) yields another dfa $\hat{M}$ such that $M$ and $\hat{M}$ are equivalent. Furthermore $\hat{M}$ is minimal in the sense ...
- 89
0
votes
1
answer
21
views
Extended transition function in NFA
The following statement seems trivial, but how can it be formally proven/argued?
$$\bigcup_{s \in \delta_{N}^{*}\left(q_{0}, w\right)} \delta_{N}^{*}(s, a) \;\equiv\; \delta_{N}^{*}\left(q_{0}, w a\...
- 89
0
votes
1
answer
66
views
Describing the Language of a DFA with 7 States
So in my attempt to convert the following DFA into a regular expression, I ended up with ((ba)*(ab(ab)*)*(aa(ba)*a)*)*. The exercise I'm following wants me to ...
- 13
1
vote
1
answer
37
views
Are both regular expressions correct for the given DFA with three states?
Are both regular expressions correct for the following automaton?
$$(\lambda+ a a^*b(ab)^*)(\lambda + b(a+b)^*)\\
\ \\
(a a^*b)^*(\lambda + b(a+b)^*)$$
The first one is the solution provided by the ...
- 89
1
vote
2
answers
46
views
Optimal way to construct union automata of two DFAs
Given two DFAs, is it also a correct method to start with the combination of the initial states of both automata, then check where I can go for each symbol from these two states. Then add the ...
- 89
3
votes
1
answer
26
views
Hopcroft's minimization algorithm produces an incorrect result for a particular regular expression
I'm writing a DFA minimizer using Hopcroft's algorithm. While testing some regular expressions, I came out with an issue in the algorithm's output relative to two particular regular expressions:
a(b|...
- 33
-1
votes
1
answer
44
views
Show that if a DFA accepts all words of length < 2n then it accepts any word
Is it true that if a given DFA $M = \langle Q, \Sigma, \delta, q_0, F\rangle$ with $|Q| = n$ accepts all strings $w \in \Sigma^*$ such that $|w|\leq 2n$ then it accepts any $w \in \Sigma^*$ ?
- 99
0
votes
1
answer
21
views
Transition System vs State Machines
Why there is no final state for a transition system? And why do NFA and DFA have final states? The transition system may or may not have any terminal states, but NFA/DFA has at least one final state (...
1
vote
1
answer
97
views
Comparing automata sizes given Myhill-Nerode equivalence under a function
Consider two finite languages, $L_A$ over alphabet $A$ and $L_B$ over alphabet $B$. $A$ might be the same as $B$.
Since $L_A$ and $L_B$ are finite languages, there exist minimal acyclic deterministic ...
- 816
0
votes
2
answers
63
views
Regex for string does not contain the substring "110"
Can anyone help me figure out the error in my approach to this problem from Sipser 1.18 (1.6f)?
Write a regular expression for the language L = {w | w does not contain 110}
So, the answer I get is: $(...
- 23
0
votes
0
answers
39
views
How to prove reverse of DFA?
How does one formally prove that, given a DFA $M=\langle Q,T,\delta,q_0,F\rangle$, the following NFA $M^R = \langle Q_R, T, \delta_R, q_R, F_R\rangle$ recognizes the reverse of M's language?
We build $...
- 99
0
votes
1
answer
48
views
How this state set of DFA was retrieved from the given NFA
I have this NFA:
1,{2, 3}
2,empty
3,{4}
4,empty
All the arrows in this NFA are epsilon-arrows.
I understand that all possible states that can be reached from each ...
0
votes
1
answer
33
views
Confused by Sipser's proof of equivalence of R and NFAs
I am reading Introduction To Theory of Computation by Sipser, 3rd Edition and am confused by his take on the last three cases of proving that "if a language is described by regular expression ...
- 23
1
vote
1
answer
34
views
What complexity class is this?
Disclaimer 1: I am a beginner in this domain and I am self-learning these concepts. Please take this in consideration when reading my question.
Disclaimer 2: All corrections to this question are ...
- 23
0
votes
1
answer
17
views
Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular (without using complement closure)
Question: Use the Pumping Lemma to show $L_1 = \Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular, for $\Sigma=\{0,1\}$ (without using the complement closure property).
My thoughts: I understand ...
0
votes
1
answer
38
views
Use the Pumping Lemma to show $\Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular
Question: Use the Pumping Lemma to show $L_1 = \Sigma^*\setminus\{0^n1^n: n\geq 0\}$ is not regular, for $\Sigma=\{0,1\}$.
My thoughts: I understand that $L_2 = \{0^n1^n: n\geq 0\}$ can be shown to be ...
1
vote
1
answer
72
views
State Complexity of DFAs for Restricted Languages
Let $\Sigma$ be a finite alphabet. All strings below are over $\Sigma$.
Definitions:
If a string $s = vw$, then $v$ is a $\textit{prefix}$ of $s$ and $w$ is a $\textit{suffix}$ of $s$.
For a language $...
- 816
1
vote
1
answer
69
views
Myhill-Nerode equivalence under a function
Consider two finite languages, $L_A$ and $L_B$, potentially over different alphabets. Now since these languages are finite, there exist minimal acyclic deterministic finite-state automata to decide ...
- 816
0
votes
1
answer
101
views
How does nondeterminism affect the power of a machine?
For example, in finite-state machines (FSM), the main difference between a deterministic (DFA) and a non-deterministic machine (NFA) is that there are possibly more branches or outputs for each input, ...
-1
votes
1
answer
40
views
Why does adding an $ \epsilon $-transition to a DFA or NFA preserve the regularity of the language?
Does adding an $ \epsilon $-transition to a deterministic finite automata preserve the regularity of the language?
Don't we have one chance to scan the word? If we choose one direction, don't we miss ...
- 101
0
votes
1
answer
57
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
38
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
80
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 ...
- 241
2
votes
2
answers
111
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
58
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
57
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
46
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
290
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
25
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
88
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
67
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
68
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
55
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
18
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
64
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
177
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 ...
- 491
0
votes
1
answer
60
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
79
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
286
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
67
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
63
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
66
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