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
67
views
Simple description of the LR(0) table generator algorithm?
I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think &...
- 111
3
votes
1
answer
765
views
When converting a epsilon NFA to NFA to DFA, how to handle the start state?
Let's say, initially we have an epsilon NFA in which the start state, say state 1, has epsilon transition to state 3
We know when converting from epsilon NFA to NFA, we apply the following formula for ...
- 305
0
votes
1
answer
218
views
Conversion of epsilon NFA to DFA, handling epsilon transitions
I am reading Michael Sipser's "Introduction to theory of computation" 3rd edition, page 55 - 56, the topic "equivalence of DFAs and NFAs"
Case 0: Michael Sipser asks us to handle ...
- 305
0
votes
2
answers
144
views
Automata: Are there algorithms to judge whether two automata are isomorphic?
When I want to judge whether two regular forms represent the same language, I have learned the next method:
create the (non-deterministic) finite-state automata which accepts the language the given ...
- 1
1
vote
1
answer
99
views
Confusion regarding "epsilon" transition in NFAs, whether taking epsilon before or after reading the input affects the final states
Let's say we have a NFA as follows:
It has 3 states, q1 - q2 - q3 and can make transition from q1 to q2 on 0 or epsilon and from q2 to q3 on 1 or epsilon
My question is do we take epsilon transition ...
- 305
1
vote
1
answer
93
views
Is the equivalence problem of a CFG and a FSM decidable?
I have the following problem:
Given a context-free grammar $\mathcal{G}$ and a finite state automaton $\mathcal{A}$, where both are over the alphabet $\Sigma=\{0, 1\}$. Is it decidable whether $L(\...
- 15
0
votes
1
answer
134
views
Confusion regarding the intuition behind epsilon transition in NFA
I am reading Michael Sipser's "Theory of Computation" 2nd edition, chapter 1 , Topic "Non determinism" ( Section 1.2 )
Let's use this E-NFA as an example
My question is, do we ...
- 305
0
votes
1
answer
166
views
When converting from nfa to dfa, do we always ignore the trap state?
Let's say we have a NFA such as follows:
We know it's equivalent DFA is follows, after minimization:
We know that when converting from NFA to DFA, the resultant DFA would have around 2^( number of ...
- 305
0
votes
1
answer
19
views
Equivalence of echo state networks and DFAs/NFAs
Echo state networks are theoretically equivalent to DFAs/NFAs, but how would you use an ESN to parse a regular language? Would you just feed many different input strings, some from the language and ...
- 11
1
vote
1
answer
51
views
Is $L = \{a^{p^2}\mid p\text{ is a prime}\}$ regular?
By pumping lemma, we choose the word $w=a^{p^2}$ that the decomposing is $[a^sa^ta^{p-s-t}]^p$
such that $u=a^s,v^i=a^t,x=a^{p-s-t}$
$[a^sa^{it}a^{p-s-t}]^p=[a^{p+it-t}]^p$
We choose i=p+1,we get $ [a^...
0
votes
1
answer
53
views
Why Regular Grammar is Left/Right Linear?
From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules)
But, my question is why it is mandatory?
Can't we ...
1
vote
1
answer
49
views
Check whether a regular expression is correct
I'm given a description of a regular language $L$, and I have a candidate regular expression $R$. Is there a systematic, step-by-step way to test whether the candidate regular expression is correct?
...
D.W.♦
- 152k
0
votes
1
answer
37
views
What characteristics would a PDA $A$ where $L(A)=\Sigma^*$ have?
I understand that the problem of whether a PDA accepts all strings is undecidable. However that doesn't mean such PDAs exist. To start, I'm working under the assumption that a PDA must read it's ...
- 11
0
votes
2
answers
143
views
If L = L1 U L2 is regular, L2 is the complement of L1 (which means L1 ∩ L2 = Ø), and we're given that L and L2 are regular, is L1 regular?
L1, L2, and L are not finite. We're given that L and L2 are regular. However, L1 ∩ L2 is empty, since L2 is the complement of L1.
Is L1 regular under the property that regular languages are closed ...
- 1
0
votes
0
answers
23
views
How are we sure choose is going to halt? question regarding a section from Elaine Rich's Automata, Computability and Complexity book?
I have a problem regarding the choose algorithm, I provide the algorithm's definition and it's use in the book,I attached a picture for the Illustration and for how the algorithm is used.
choose (x ...
- 11
4
votes
0
answers
76
views
Inverse operation to concatenation for regular languages
I'm currently in need of the inverse operation of the concatenation of 2 regular languages.
Formally, for 3 regular languages $A,B,C$ such that $A \cdot B = C$, only $A$ and $C$ are known, and $B$ is ...
- 113
0
votes
1
answer
50
views
Why must 2 distinct strings go to the same state in a DFA?
I'm finding it difficult to understand why due to the pigeonhole principle, 2 distinct words must go to the same state in a DFA.
Is it that if there are n words and m states, where there are more ...
- 1
0
votes
0
answers
18
views
complement of {a^lb^mc^n:n>l+m}
If we have this language $ L = \{a^mb^nc^n:m,n \in N\}$, would its complement be $\{a,b,c\}^* \setminus L = L^\complement = \{c^nb^na^m:m,n \in N\}$? This was the professor's answer, which I find ...
- 1
0
votes
2
answers
91
views
Regular language under intersection and complement confusion
I know that regular languages are closed under closure properties. But, for example, we know if $L$ is regular, then its complement $L^\complement$ is also regular. If we have $L_1$ and $L_2$ as ...
- 33
0
votes
1
answer
61
views
Exists and forall in formal language definition in the case of kleene star [closed]
Let's suppose we have language $Y = \{a^ib^j:i,j \in N^*\}$ defined over the alphabet $\Sigma^{}_{} = \{a, b\}$
If we want to define this language $\Sigma^{*}_{}$ \ $\ Y$ such that we don't have the ...
- 33
0
votes
0
answers
62
views
How to find the intersection of two FAs and then check if two FAs are equal?
I am still quite confused on how to properly handle in answering the intersection and equality of two FAs in terms of table form and manipulating its transformation....
- 13
0
votes
1
answer
28
views
Finite Automata Mixture Combinatorics
Hello Folks,
I am facing hard time in understanding this, basic question which says, how many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with ...
0
votes
2
answers
406
views
DFA and NFA Equivalence Proof
I'm taking a Theory of Computation class and we went over the proof to show that for any NFA there is an equivalent DFA, which I understand the proof fully in this case. But if it were in reverse, for ...
- 1
0
votes
1
answer
34
views
Models of computation less powerful than DFA
I wonder if there are "standard" models of computation that are less powerful than DFA that are still "mathematically interesting"? It is evident that restricting the set of DFAs ...
- 101
1
vote
1
answer
27
views
Compressed string lookup by name or ordinal
I have a large list of strings with associated values. I need to do a fast lookup into the list by the string prefix, but also by the string's ordinal within the list. For example,
...
- 129
0
votes
1
answer
101
views
How to convert the regular expression $\emptyset^*$ to an NFA?
The question is to convert the following regular expression to an NFA: $\emptyset^*$.
I know that the symbol phi in Theory Of Computation means an empty set. But what does phi^* mean?
0
votes
1
answer
71
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.
...
- 103
1
vote
1
answer
73
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 ...
- 113
1
vote
2
answers
118
views
does finite automata 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 ...
- 115
0
votes
0
answers
29
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
72
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
90
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
157
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
47
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
60
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
144
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
71
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
44
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
108
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 ...
- 911
0
votes
2
answers
2k
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: $(...
- 33
0
votes
0
answers
69
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
55
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
43
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 ...
- 33
1
vote
1
answer
54
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
31
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
62
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
80
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 $...
- 911
1
vote
1
answer
83
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 ...
- 911
0
votes
1
answer
180
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
129
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