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
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?
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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) ? ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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$...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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!
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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^*)$ ...
user avatar
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, \...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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}$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
  • 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&...
user avatar
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 ...
user avatar
-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 ...
user avatar
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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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.
user avatar
  • 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}\...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
  • 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\}$$ ...
user avatar
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$: <...
user avatar
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....
user avatar
  • 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$, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
-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 ...
user avatar

1
2 3 4 5
33