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,674
questions
2
votes
1
answer
69
views
Regex where all strings containing an even number of 0's:
Question is to construct a regex where all strings containing an even number of 0's:
By constructing DFA graphically, it is
$$(1^*+01^*0)^* $$
But it is also
$$1^*(01^*01^*)^*$$
Can we prove that they ...
- 55
0
votes
0
answers
9
views
RE to NFA conversion JFLAP [closed]
Having this regular expression ((0 + 1)(11)* + 0)* I get this NFA according to me:
I'm trying to compare it with the RE on JFlap and it says it's not equivalent ...
- 11
1
vote
2
answers
57
views
Need to create CFG that requires sum of other letters
I have a homework assignment that requires me to create CFG $G$ for
$$L = \{a^i b^{i+j+k} c^j d^k\}$$
so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or ...
- 11
3
votes
3
answers
1k
views
DFA that accepts strings whose 10th symbol from the right end is 1
Problem is "Constructing a DFA accepting set of all strings whose 10th symbol from the right end is $1$ over $\{0,1\}$"
The NFA is easy
$$(0+1)^*1(0+1)^9$$
but DFA has to have minimum $2^{10}...
- 55
1
vote
2
answers
52
views
Finite state machine that accepts every word with at least one c, or different value of parity of the counts of a's and c's
few weeks ago I had an exam in automata theory course and I've been asked to write the following non-deterministic finite automata
Write a NFA which accepts the following language - the language ...
- 11
3
votes
1
answer
612
views
Can we transfer every DFA to DFAs with start state having no in edge?
The start state cannot have any "in edge" (an arrow point directly to the start state) and only out edge is possible for the start state. Other states except the start state are free of ...
1
vote
1
answer
61
views
Transform a non-regular language into a regular one using sort
Is there a way where sort turns a non regular language into a regular one.
What I mean by sort is this:
Consider the language $L =$ { $bac, cbca, acbb$}. $sort(L) = $ {$abc, abcc, abbc$} respectively.
...
- 13
-1
votes
0
answers
43
views
Intermediate DFA question- divisibility
The question is
"The set of strings such that the number of 0's is divisible by five,
and the number of 1 's is divisible by 3 over the alphabet {0,1}"
All I could do is just 0's that are ...
- 55
0
votes
1
answer
46
views
Is there a typo in this excerpt from the book?
Michael Sipser's Introduction to Theory of Computation:
Is there a typo in the highlighted line? I ask that because near the beginning it says that R is a set of states of N, and that R itself is a ...
- 3
1
vote
1
answer
66
views
Constructing a deterministic finite automaton from a particular regular expression
This is the given question-
Construct a DFA over the alphabet {0,1} such that it accepts all strings containing
even number of 0's OR the number of 1's divisible by 3.
The very first problem I've ...
- 11
2
votes
0
answers
145
views
What extension of a finite-state machine is modeled by aliasing inputs?
Recently, I’ve been interested in the console of the Source game engine, more specifically, its alias command, which allows one command to invoke others. It may ...
- 21
-4
votes
1
answer
38
views
Describe the language accepted by the DFA
Describe the language accepted by the DFA shown above
0
votes
1
answer
49
views
Is pumping lemma not applicable for every 'long enough' string in the language?
I recently learnt that a subset of a regular set may not be regular. This is causing me confusion as I imagined if a set is regular then every string longer than $p$ can be pumped in the language. So ...
- 15
1
vote
1
answer
60
views
What are non-isomorphic NFAs
I came across the following problem while doing my Formal Language class assignment and hope someone can give me some hints:
I have $\Sigma = \{0,1\}$ and $L=\{x0a \mid x \in \Sigma^*, a \in \Sigma\}$...
- 15
0
votes
1
answer
43
views
Algorithm to determine the regularity of a language
According to the answer provided by Janoma, there are several methods to determine the regularity of a language.
Theorem
Let L ⊆ Σ∗. The following conditions are equivalent:
L is generated by a ...
0
votes
2
answers
63
views
Can a DFA have multiple of the same state?
I need to create a DFA for a sequential order of states e.g.
A -> B -> C -> B -> A
and so on, where 'A' is the start and finish state,
1 is a transition to the next state and 0 just loops ...
0
votes
1
answer
63
views
Explain meaning of states and transitions for DFA that accepts two binary words (a,b) with b = 5a
I was provided with the solution to the language being represented. An example of accepted input would be [001][101]. The DFA that would recognize this language is below.
What do the states represent?...
- 11
1
vote
1
answer
95
views
Getting an NFA with only one initial and final state without epsilon transitions
Given an NFA with more than one initial or final state, it is possible to convert it to another NFA with only one initial or final state by using epsilon transitions. To remove the epsilon transitions,...
- 115
0
votes
1
answer
29
views
Designing DFA for a language
I am working on designing a DFA with the language $a^i b^j c^k$ such that $i + j + k$ is odd
I thought along the following lines:
$i+j+k$ is odd $\Rightarrow$ two of them are even and one is odd or ...
- 131
1
vote
1
answer
89
views
How to design a DFA that accepts the language of pairs of binary words (a,b) with 5a=b?
Let $\begin{bmatrix}0\\ 0\end{bmatrix}$ be a two-column vector with $0$ in the first row and $0$ in the second row.
Let $\Sigma_2 = \left\{
\begin{bmatrix}0\\ 0\end{bmatrix},
\begin{bmatrix}0\\ 1\end{...
- 11
0
votes
0
answers
33
views
prove that Every DPDA has an equivalent DPDA that always reads the entire input string
I am reading Michael Sipser's book Introduction to the Theory of Computation and in the section 2.4(chapter 2 and DCFLs section) there is a proof for the lemma that says "Every DPDA has an ...
- 1
1
vote
1
answer
101
views
What is the smallest NFA you can design for {a^n : n =/= 1003}
What is the smallest NFA that could be design for a^n where n!=1003?
I have been racking my brain at this for a while but still can't reduce the number of states required from 1004. Here state(1003) ...
- 13
0
votes
0
answers
32
views
Is there any way to tell which states are final states in a finite state automata given only its grammar?
Problem
In the problem, I was given the grammar for a non-deterministic finite state automata (NDFSA). There was no other useful context given. The problem asks you to use this grammar to draw the ...
-4
votes
2
answers
73
views
A string that contains aabb, does this work?
Can you verify this like please bro please tell me the answer to my question
- 1
3
votes
1
answer
62
views
Building the minimal automaton from the syntactic monoid of a language
I'm studying the algebraic view of automata theory. One of the basic results is that the syntactic monoid of a language $L$ is the transition monoid $M(A)$ of the minimal automaton $A(L)$ accepting $L$...
- 448
0
votes
0
answers
23
views
Meaning of term $L(\bar{n})$
I was studying a few terms on finite automatas, and came across the following terms:
$L(\bar{n})$ and $\overline{L(n)}$
The latter term stands for complement of a given NFA, but what does $L(\bar{n})$ ...
- 115
0
votes
2
answers
57
views
Every DFA accepting a finite language must contain a dead state?
I came a across a question where there were some statements made on Finite Automata, DFA and their states.
One such statements in the question was that a "Every DFA accepting a finite language ...
- 115
0
votes
0
answers
35
views
How does the regular expression '^(a+)+$' lead to this specific NFA?
OWAPS has an article on ReDoS (archived).
In it, they use the regular expression ^(a+)+$ as an example for ReDoS vulnerabilities.
They provide this illustration of ...
- 101
-1
votes
1
answer
25
views
find the minimization of the dfa
so this is the question , I have to minimize this DFA
this is How I did it
but when I checked for answers , this is what it was,
can someone please explain to me what mistake I made? I have been ...
0
votes
0
answers
23
views
In Pumpin Lemma, let's say we have a decomposition of the string s = xyz, is it necessary for x to take the automaton through distinct states?
I understand what Pumping Lemma is, how it works and also understand it's proof. The gist is that it uses "Pigeon Hole" principle to guarentee us a repeatation in the sequence of states and ...
- 305
0
votes
1
answer
40
views
Does every regular expression describe only 1 language?
If we have a regular expression $R$, will $R$ describe only regular language $L$, but that language $L$ can have multiple different regular expressions such as $Q,W,A,S,D \ etc..$ describing it
Also, $...
- 305
-1
votes
3
answers
49
views
Is it possible to divide a string, according to pumping lemma, from a language in a way that pumping a section would render the language -non regular
I understand that pumping lemma can only be used to prove that a certain language is "non-regular", it cannot be used for proving regularity
But since, it's a property of regular language, ...
- 305
0
votes
1
answer
52
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
470
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
171
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
119
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
74
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
76
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
106
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
73
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
14
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
49
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
44
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
39
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.♦
- 150k
0
votes
1
answer
33
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
105
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
22
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
70
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 ...
- 103
0
votes
1
answer
44
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
17
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 ...
