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.

Filter by
Sorted by
Tagged with
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 ...
-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 ...
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 ...
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, ...
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?
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 ...
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) ? ...
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 ...
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 ...
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, ...
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^*)$ ...
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, \...
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 ...
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 ...
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 ...
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

1
2 3 4 5
33