All Questions
Tagged with dfa or finite-automata
1,820 questions
-3
votes
0
answers
42
views
Theory Of Automata [closed]
Each of the following languages is the intersection of two simpler languages. In
each part, construct DFAs for the simpler languages, then combine them using the
construction discussed in footnote 3 (...
- 1
-1
votes
0
answers
25
views
Constructing a Non-Deterministic Automaton Based on Length
Hey given 2 regular language L1,L2 I need to show:
L = $\{w \in L(A) \text{ and } \exists y \in L(B) \text{ such that } |w| > |y|\}$
I thought about defining the new automate like this:
$Q= Q_a\ x \...
- 99
7
votes
2
answers
1k
views
Does there exist a unique minimal DFA with more than one start state?
Given a regular language $L\subseteq\Sigma^*$, there exists a unique minimal DFA with minimal number of states that accepts $L$.
On the other hand, it is well-known that there does not exist a unique ...
- 193
3
votes
3
answers
254
views
Can one prove directly that the language given by a regular grammar is the language given by some regular expression?
The let $L$ be a language. The following are equivalent:
$L$ is given by a deterministic or non-deterministic finite accepter.
$L$ is given by a regular grammar.
$L$ is given by a regular expression.
...
- 177
0
votes
1
answer
27
views
If the start state of an NFA is also an accept state, what happens when the input does not have transition to another state?
I am having some trouble understanding Figure 1.36 in Sipser's book. It deals with a simple NFA that accepts strings epsilon, a, baba, and baa. But rejects strings b, bb, and baa
But q_1 does not ...
1
vote
1
answer
238
views
Why is this grammar context-sensitive?
Working on: Richard Johnsonbaugh. (2018). Discrete Mathematics, 8/e (p. 607)
2. Determine whether the given grammar is context-sensitive, context-free, regular, or none of these. Provide all ...
- 139
-2
votes
1
answer
53
views
Conversion of RE into finite automata
Is this conversion of the regular expression L(((011 + 11)∗(00)∗)∗) into the transition diagram of a finite automata good? Please guide me into what could be wrong, I did it two times differently.
0
votes
1
answer
36
views
Can a DFA have no transitions to just accept the empty word?
Online, I only find DFAs that have two states and one transition to accept: $\{ \epsilon \}$, so one state is accepting and the other acts as a dead state where everything that is not the empty word ...
- 31
1
vote
1
answer
68
views
Arden's Theorem Proof [closed]
Arden's Theorem: Let $P$ and $Q$ be regular expressions over $\sum$ such that $P$ does not contain the null string. Then, the equation $R = Q + RP$ has a unique solution $R = QP^*$.
Proof: Substitute $...
- 13
0
votes
1
answer
54
views
Informal Description of a Non-Deterministic Turing Machine (NTM) for a Language
I need help describing a Non-Deterministic Turing Machine (NTM) for the following language:
$L=\{(ww^c)^n | n>1$ and $w,w^c\in\{a,b\}^*\}$. If $w=w_1...w_k$ then $w^c=w_1^c...w_k^c$ where $w_i^c=b$ ...
- 1
0
votes
0
answers
47
views
Informal Description of a Deterministic Turing Machine for a Specific Language
I'm working on a problem that asks for an informal description of a deterministic Turing Machine (TM) for the following language:
$L=\{a^i b^j a^k b^l | i+j=k+l\}$
The challenge is to describe how a ...
- 1
0
votes
2
answers
113
views
Pumping Lemma does not disprove this language is regular
Using the alphabet $\Sigma = \{b_1, b_2, \ldots, b_n\}$ which consists of $n \geq 5$ symbols, prove that
$$
L = \{ w \mid \text{there are at least two different symbols } b_x, b_y \in \Sigma \text{ ...
- 31
2
votes
1
answer
95
views
Implementing a TM with FIFO Machine
I am attempting to simulate a TM on a FIFO machine. My initial approach is the following:
\begin{align*}
\text{Starting string:} & \quad \text{uabv}\rightarrow bv\#ua \\
\text{Step 1:} & \quad ...
- 21
2
votes
1
answer
76
views
Complexity of identifying "generic & distinguishable" Moore machines
Consider a non-deterministic Moore machine with input alphabet
$\Sigma
\newcommand\OO{\mathcal{O}}
\newcommand\o{\mathfrak{o}}
\newcommand\PP{\mathcal{P}}$ and output alphabet $\OO$, a set of states $...
- 31
2
votes
1
answer
54
views
pumping lemma, |xy| ≤ p and cycles
By looking at wiki and other question, I understand $x$ is the string drive to first repeated state $q$ from starting state, and $y$ is the string that cycle back from $q$ to $q$, and $p$ is the ...
- 23
4
votes
1
answer
85
views
Why are (finite word)Büchi sets closed under iterated sums?
For a language recognizable by a DFA, we associate a subset of natural numbers with it. These numbers correspond to the strings accepted by the DFA (consider the binary alphabet, so each word is just ...
1
vote
2
answers
67
views
Counter automaton that recognises $\{ x\ a\ x^T | x \in \{0, 1\}^*, a \not\in \{0, 1\}\}$
I've been recently reading literature on counter machines, and stumbled across Counter Machines and Counter Languages by Fischer, Meyer, and Rosenberg [1].
In Theorem 1.3, they give an informal ...
- 13
0
votes
0
answers
27
views
Design a nondeterministic Turing machine that the tape head move to the right of the input in exponential time
More specificly, I want a nondeterministic Turing machine(NTM) $N$ such that for every input $w$ of length $n$, the tape head is initially on the first letter. The transition allows the head to move ...
- 1
0
votes
2
answers
233
views
Regular expression for a language that has equal number of ‘01’ and ‘10 substrings?
My understanding so far:
At first glance, it seemed like I had to keep track of all occurrences of ‘10’ and ‘01’ but that is not the case. At any given point, there are only three possibilities. ...
2
votes
2
answers
82
views
Making a CFG for $L = {a^i b^j c^k d^m : i + 2j = 3k + m; i, j, k, m>= 0}$?
I am trying to construct a context-free grammar (CFG) for the following language:
$L = \{a^i b^j c^k d^m : i + 2j = 3k + m; \, i, j, k, m \geq 0\}$
So far, I've tried doing something like this:
$S =...
- 21
2
votes
1
answer
55
views
Minimal DFA for Counting Distinct Symbols Modulo 3
I am seeking a minimal Deterministic Finite Automaton (DFA) that determines the number of distinct symbols in a given word, modulo 3, over an alphabet of size N.
Specifically, the DFA should have the ...
- 371
0
votes
1
answer
46
views
Finding the output string corresponding to an input string for a finite-state machine
Working on:
Richard Johnsonbaugh. (2018). Discrete Mathematics, 8/e (p. 590)
I am studying finite-state machines, and I have the following definition in my book:
Definition 12.1.8
Let $M = (I, O, ...
- 139
0
votes
0
answers
15
views
Prove the existence of 2 specific lenghted words given a DFA
Let $A$ a DFA with $n$ states.
Prove:
If $|L(A)|=\infty \implies \exists w,w'$ s.t $0\leq |w|-|w'|\leq n$ and $|w|\leq 2n$.
The part I'm not so sure about is the one where I pick $w_1,w_2$. I'm not ...
- 169
0
votes
1
answer
21
views
I can't understand the definition of the language of NFA
I'm reading "INTRODUCTION TO Automata Theory, Languages, and Computation" by Hopcroft, Ullman and can't understand the definition of the language of NFA.
It says:
$$L(A)=\{w| \hat{\delta}(...
- 11
0
votes
0
answers
26
views
How to tell if the language of one regular expression exsit as subtrings in the language of another regular expression (behavior aspect)?
I'm just wondering if there is an algorithm to efficiently check if the language of one regular expression exists as substrings in the language of another regular expression.
The set of all strings ...
- 1
1
vote
1
answer
100
views
$L'=\left \{ z^Rx : xyz\in L \right \}$ is regular
Let $L$ be a regular language over $\Sigma = \left \{ 0,1 \right \}$.
The question asked to show that $L'=\left \{ z^Rx : xyz\in L \right \}$ where $x,y,z\in \Sigma^*$ is regular.
What I tried
$L$ is ...
- 191
0
votes
1
answer
55
views
Confusion regarding the conversion of epsilon-NFAs to non-epsilon NFAs
I've begun reading up on NFAs and DFAs, NFAs of both the epsilon and non-epsilon kind
My understanding of epsilons are this: They help 'encode' the idea of taking another optional route without ...
- 103
-1
votes
2
answers
66
views
Myhill-Nerode sentence and the relation $R_L$
Given a finite alphabet $\Sigma$ of size $n\geq 1$, we define the following language over $\Sigma$:
$$L = \left\{ u \sigma v \sigma w \mid \sigma \in \Sigma, u, v, w \in \Sigma^* \right\}
$$
Let $R_L$ ...
- 31
3
votes
0
answers
125
views
Convert a regular expression to a *minimal* LL(1) regular grammar
Given a regular language defined by a regular expression, we can convert it to an NFA, which is equivalent to a right-regular grammar. The grammar is not generally LL(1).
However, if we convert the ...
- 151
1
vote
1
answer
157
views
What is the connection between a regular language's pumping number, and the number of states of an equivalent deterministic automaton?
I am self-studying Automata and Formal Languages from a set of past lecture notes, and I have a question about the proof of the Regular Pumping Lemma. The proof defines $D$ to be a deterministic ...
2
votes
1
answer
28
views
Complexity of deciding if a DFA is counter-free
It is well-known that deciding whether an NFA or a regular expression define a counter-free/star-free language is PSPACE-complete.
Does the problem become easier if I have a DFA as input? What's the ...
- 548
4
votes
1
answer
105
views
$L'=\left \{w : w\cdot Drop_a(w)\in L \right \}$ is a regular language
$\Sigma=\left \{ a,b,c \right \}$.
For a string $w\in \Sigma^*$, $Drop_a(w)$ is the string $w$ after we remove all occurrences of "a" from it.
The question asks to show that if $L$ is a ...
- 191
1
vote
2
answers
64
views
Creating a DFA where the string should start with b and the length is 3
I'm new to automata and in my first exercise I have to construct a DFA that starts with 'b' and length=3. Two symbols (a,b).
To my understanding, there are 4 possibilities {baa,bab,bba,bbb}
I have ...
- 21
3
votes
1
answer
49
views
Do all regular languages have a backwards deterministic FSM with one initial state and no $\varepsilon$-transitions?
There's been a question about an algorithm converting an arbitrary FSM into a backwards deterministic automaton without $\varepsilon$-transitions and a single initial state.
As commenters pointed out, ...
- 1,624
5
votes
1
answer
145
views
Is there an algorithm to turn any finite automata into a backwards deterministic one, with no $\epsilon$ transitions, and only one initial state?
An automaton is backwards deterministic if, for all states q, p, for all symbols a:
$$
(\delta(q, a) = \delta(p, a)) \implies p = q
$$
(I think the right translation is backwards deterministic, but ...
- 53
2
votes
1
answer
49
views
FSA for 'closure' of a language; how to represent?
Is my interpretation of this correct?
I want to represent a regular language, L(B) as L(A*) where L(A*) represents the closure of L(B), as a DFA.
In order to do so, would I draw a new edge from the ...
- 109
0
votes
1
answer
62
views
How is L = a^2n regular if it doesn't pass the pigeon-hole principle test?
I understand that this topic has been discussed, and I have reviewed numerous posts about it on stack overflow. However, my question remains unresolved. Specifically, I am seeking clarification on the ...
- 11
2
votes
2
answers
81
views
Is garbage state necessary in DFA that enforces a particular input combination?
If I have the regex 1(0+1)* for example, then should my DFA have an arrow leading away from the starting state for when the first input is 0? I see that this regex ...
- 109
4
votes
1
answer
262
views
Is it possible to have intersection of L1 and L2 DFA contain states with no input edge?
I am doing a HW problem where I have L1 and L2.
I did the product construction method to produce all the new states of the DFA representing L1 and L2 (the number of states in L1 times the number of ...
- 109
0
votes
0
answers
31
views
Does a Moore Machine always require an output for start state?
My lecture notes show all moore machines as having an output even for q0, the starting state.
This video shows a Moore machine without an output for its starting state.
I understand that all Moore ...
- 109
2
votes
1
answer
47
views
Lower bound states for NFAs: seeking examples and methods
We can establish some lower bounds for DFAs recognizing specific languages. For example, we can show that there exists a language $L_n$ such that every DFA recognizing it has at least $2^n $ states. ...
1
vote
2
answers
127
views
Quickly converting a regex into a minimized DFA
Is there some sort of algorithmic way to quickly convert a regex into a minimized DFA? I am able to somehow "guess" the DFA by playing around with the regex (as shown in the image, where the ...
0
votes
1
answer
72
views
Proof that $ALL_{DFA} \in SPACE(log^{2}n)$
we define $ALL_{DFA}$ as:
$ALL_{DFA} = \{ <A> | \text{ A is a DFA and L(A) = }\Sigma ^ {*} \}$
I'm looking for a proof that $ALL_{DFA} \in SPACE(log^{2}n)$ where n is the number of states in the ...
- 119
0
votes
1
answer
34
views
Question about a grammar who generates $(0+1)^*$
On a test from my Automata theory class of last year, I have seen an excercise that gives the free context grammar $G$ with the following rules:
$$S \rightarrow 0S1 | S0 | 1S | \varepsilon$$
and asks ...
- 123
5
votes
1
answer
64
views
What is the name of a DFA where all long enough words are synchronizing words?
TLDR: What is the name of a DFA that satisfies the following property: "I can guarantee that after feeding the automaton $n$ random symbols it will end up at some state that does not depend on ...
- 153
-1
votes
3
answers
288
views
Design a DFA that accepts even length binary strings that start with 0 and must not contain substring "001"
it will reject strings such as 001, 0001, 0010, 001001
Accepts = {00, 01, 0111, 0101, ..}
2
votes
1
answer
775
views
PDA for Palindrome Strings
I am studying Automaton Theory for first time and I am having problems to see if I do well some exercises and if I really finish them. For example, one exercises asks to give a PDA for all palindrome ...
- 123
0
votes
1
answer
281
views
PDA for $\{a^i b^j c^k : i \neq j \}$
I am trying to write a PDA for $L := \{ a^i b^j c^k : i, j \in \Bbb{N} \land i \neq j \}$, but I am getting stuck since I am new with Automaton Theory. My idea was to make PDAs for both $\{ a^i b^j c^...
- 143
1
vote
1
answer
89
views
How to formally prove that any regular expression can be written as a finite combination of base cases and operations?
In Michael Sipser's book, "Introduction to the Theory of Computation," regular expressions are defined as follows:
Based on this definition, how can I formally prove that any regular ...
- 113
0
votes
4
answers
218
views
Proof that the mind/brain is not a finite state machine by recognizing an unrecognizable language?
Some people believe the human mind is a finite state machine, making references to the Bekenstein bound. I've read that Turing himself imagined the human as FSM with unbounded paper to construct the ...
- 326