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,728
questions
-1
votes
2
answers
109
views
Create DFA such that every substring of w of length 3 contains two or three 0's with w={0,1}
I am attempting to draw the DFA of this problem but I'm kind of stuck. In another post I saw that the DFA should have 10 states. I'm finding it hard to even understand the question, is the input to ...
- 28.4k
1
vote
2
answers
236
views
Create a Deterministic Finite Automaton for a regular expression
I want to create a finite state machine that accepts the following language:
$$
L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}
$$
So I began by writing a regular expression ...
4
votes
1
answer
139
views
Simultaneous reachability of NFA states
Suppose I have a $n$-state non-deterministic finite automaton $F$ over alphabet $\Sigma$. Let $S(x)$ be the set of states reachable from the starting state by consuming string $x$.
I am interested for ...
CommunityBot
- 1
2
votes
1
answer
12k
views
What is the difference between transition function (delta) and extended transition function (delta hat) in finite automata?
What is the difference between transition function delta ($\delta$) and extended transition function delta hat ($\hat{\delta}$) in finite automata?
Both of them, when started at a state $q$ for a ...
CommunityBot
- 1
1
vote
1
answer
60
views
DFA for even concatenation of strings from a language
If I have a deterministic finite automaton (DFA) with a language $W$, and I need to create another DFA that returns all the strings that are a concatenation of an even number of strings in $W$, how ...
0
votes
1
answer
137
views
nfa of the Language L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive
I have a question I need to give the NFA of the following language: L={w belongs to (a,b)*/w starts with aa or ends with aa} with or being not exclusive meaning I can have a word that starts with aa ...
CommunityBot
- 1
0
votes
1
answer
1k
views
Determine if an NFA accepts infinite language in polynomial time
Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite.
(Note that converting NFA to DFA is exponential time).
For any DFA,...
CommunityBot
- 1
1
vote
2
answers
7k
views
DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?
Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we ...
1
vote
1
answer
22
views
Does there exist terminology to discern NFA states and NFA-transformed-into-DFA state?
I can't find this from surface search in the literature
When one observes/simulates NFA after processing several characters, one has to consider both "internal states of NFA" (individual ...
CommunityBot
- 1
0
votes
1
answer
93
views
Intersection of Infinite Regular Language with CFL
Intersection of any finite regular language with anything( CFL or not CFL) will be finite but what about intersection of infinite regular language with CFL or not CFL. Does the resultant will be ...
CommunityBot
- 1
0
votes
0
answers
32
views
1 way 2 stack and 2 way 2 stack Pushdown Accepters that accepts L={a^(n^2)|n≥1}
Using a 1 way 2 stack, and a 2 way 2 stack PDA, I want to check if the length of a an input string is strictly a perfect square number. How can I do this in both approaches?
1
vote
1
answer
533
views
Converting DFA to Regular Expression Using State Removal
I'm trying to convert the following NFA to a regular expression.
I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
CommunityBot
- 1
0
votes
2
answers
42
views
Why does lexer has O(n) time complexity?
According to my CS knowledge so far, a lexer uses DFA(which takes linear time) for 'each' token type to find the next token, so in the worst case, it should try 'all possible' token types of a ...
0
votes
1
answer
78
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?...
CommunityBot
- 1
0
votes
2
answers
70
views
How to find prefixes and suffixes for infinite languages? (Automata)
L= {abc}
prefix = {epsilon,a,ab,abc}
suffix = {epsilon,c,bc,abc}
It's easy to find suffixes and prefixes for finite Regular languages. But what will be the ...
- 663
0
votes
1
answer
79
views
What could be possible NFA for the RegEx "a?"
I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$
I am wondering if I should deconstruct the RegEx as -
Concatenation of $a+$, $(b|c?)$ together with $c$ OR
...
CommunityBot
- 1
0
votes
0
answers
62
views
Turing machine for a^n b^m c^n d^m
The state diagram for the initial part of this turing machine given as:
Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
- 101
12
votes
1
answer
7k
views
If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$
I am interested in proving that $\sqrt{L}=\{w:ww\in L\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right ...
- 275k
3
votes
2
answers
2k
views
Determining Length of a walk in Nondeterministic Finite Automata with Lambda Transitions
I am learning about CS Theory and specifically Nondeterministic Finite Automata (NFA) right now. In my book I came across a section of text that discussed a way to determine the length of a walk ...
- 275k
1
vote
3
answers
2k
views
Length of distinguishing string for a DFA
Is it possible for a $DFA$ which has $n$ states that, there exists two distinguishable states $p, q$ such that there exists a distinquishing string between $p$ and $q$ whose length is greater than $n$?...
- 275k
6
votes
2
answers
4k
views
Are all DFAs also NFAs?
Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?
- 1
0
votes
1
answer
605
views
Can we skip an input in push down automata
Hi here I'm giving a language
L3={0^m 1^(n ) 2^m | m,n ∈ N}
I designed this stack machine in order to accept this given language.
Here I'm skipping 1 (no matter how many 1s are there) . Is it ok to ...
CommunityBot
- 1
0
votes
0
answers
27
views
What is the minimum length word accepted by the product of these simple loop automata?
Let $A_{n} = (aa|aaa|aaaa|\dots |a^{n-2})(a^{n})^* $ where $n \geq 4$ is some natural,and $A_2 = (a^2)^*, A_3 = (a^3)^*$. Clearly every transition is thus labeled by an $a$. From now on let $A_n$ ...
- 495
2
votes
1
answer
66
views
What is the Minimum length of a string that is accepted by a DFA that shows that the language accepted by that DFA is infinite?
What is the minimum length of a string that is accepted by a DFA, shows that the language accepted by that DFA is infinite?
I checked this post How to determine if an automata (DFA) accepts an ...
- 28.4k
0
votes
1
answer
61
views
Construct a regular grammar that produces all possible strings of $\Sigma = \{a,b\}$ that do not contain substring 'abba'
I'm really stuck here and do not know what to do. So far, I've constructed a DFA and a regular expression that produces the aforementioned set of strings. Namely, the DFA looks like:
After a lot of ...
D.W.♦
- 156k
7
votes
1
answer
289
views
A Turing machine with each cell accessed at most $10$ times has an equivalent NFA
I am confused by the following claim:
Let $T$ be a (decider, single-tape) Turing machine with the property that for every input, every cell on its tape is accessed at most $10$ times. Then there is a ...
CommunityBot
- 1
3
votes
1
answer
181
views
NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?
I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s_i, q_i)$, where $s_i$ are binary strings and $q_i$ are states (we are ...
CommunityBot
- 1
0
votes
0
answers
43
views
After converting a CFG to a PDA, what is an example input string to the PDA?
For example, the following CFG:
S$\rightarrow$aSb|$\epsilon$
A valid string within the language described by the CFG would be, e.g., "aabb".
The converted PDA has the following form:
The ...
- 111
0
votes
0
answers
40
views
Binary combinatorics with rank
I am looking at finding acceptable binary values with maximum 2 consecutive 1s and 0s, from a range of maximum 6 bits (2^6 values).
Also, I want to rank and unrank these subset of values (in ...
- 23
0
votes
0
answers
27
views
DFA for "K" bit value with max "n" consecutive "0"s and "1"s
I had posted earlier a question regarding ranking max "n" consecutive "0"s and "1"s in a "K"-bit string -
Order in a subset
I got clarification regarding how ...
- 23
0
votes
1
answer
71
views
Question about remainder in automata construction that checks divisibility
I'm trying to understand de construction of a DFA from the book "Introduction to Automata Theory, Languages, and Computation by John Hopcroft and Jeffrey Ullman 1st ed"
It says:
Where it ...
- 101
0
votes
0
answers
60
views
Minimum number of states in a DFA
Consider the language L given by the regular expression (a + b )*b(a + b) over the alphabet {a, b} . The smallest
number of states needed in a deterministic finite-state automaton (DFA) accepting L is ...
- 1
0
votes
0
answers
48
views
How to convert a NFA to alternating finite automata AFA?
I am trying to construct an AFA from a NFA, how do I know if a state of NFA becoms existential or universal in the AFA?
- 1
0
votes
1
answer
81
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 &...
CommunityBot
- 1
2
votes
1
answer
202
views
Is it possible to create a NFA that accepts only n*"a" or n*"b" inputs?
I'd like to create a NFA that accepts only inputs like "aaaaa";"a";"bb";"bbb", but not like "aab";"aabaa".
Is the even possible? As far as I ...
CommunityBot
- 1
1
vote
2
answers
82
views
Is my regular expression and finite automata diagram for this state table correct?
So i have some theory of computer science homework and I'm struggling with this question currently. I am given the following automaton:
$Q = \{q_0,q_1\}$.
$\Sigma = \{a,b\}$.
$q_0 = q_0$.
$F = \{q_0\}...
CommunityBot
- 1
4
votes
1
answer
69
views
Translating non-deterministic finite automata with counters to deterministic ones
I know there are algorithms for translating regular NFAs into their corresponding DFAs. Can these algorithms be applied to automata that employ transitions involving counters in a straightforward way, ...
D.W.♦
- 156k
32
votes
4
answers
7k
views
How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?
I created a simple regular expression lexer and parser to take a regular expression and generate its parse tree. Creating a non-deterministic finite state automaton from this parse tree is relatively ...
- 17.7k
0
votes
1
answer
337
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 ...
CommunityBot
- 1
0
votes
1
answer
131
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 ...
CommunityBot
- 1
2
votes
0
answers
34
views
Let $∑$ be an alphabet. Is the set of all DFAs over $∑$ countable?
Let $∑$ be an alphabet. Is the set of all DFAs over $∑$ countable?
I know the set of all regular languages is countable, however, it is impossible to build an injection from the DFAs to the regular ...
- 135
1
vote
1
answer
195
views
Pumping Lemma $A = \{0^n1^n \mid n \geq0\}$. Prove $A$ is not regular
Question : Are my Justifications Correct?
Pumping Lemma
$A = \{0^n1^n \mid n \geq 0\}$. Prove $A$ is not regular :
Suppose $S = 0^p1^p$ and $p = 3$.
Therefore, $S = 000111$. Breaking $S$ into $xyz$
...
CommunityBot
- 1
0
votes
2
answers
36
views
Linked Finite State Machine
Let us assume, we have a FSM (to be precise, an epsilon-NFA) in which I've got redundant structures.
I am looking for a framework that allows to factor out the redundant part into some kind of ...
- 663
0
votes
1
answer
24
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 ...
CommunityBot
- 1
0
votes
1
answer
122
views
Copy operation in under 9 states?
There is a long row of cells. Each cell contains 0 or 1. A machine is positioned immediately to the right of a series of uninterrupted 1’s followed by an uninterrupted series of 0’s. In the following ...
CommunityBot
- 1
0
votes
1
answer
55
views
What strings are accepted by the described DFA?
Could someone clarify what strings are accepted by the described DFA?
Draw a DFA for the set of all strings with two consecutive 0’s followed by two consecutive 1’s over Ʃ= {0,1}
CommunityBot
- 1
0
votes
0
answers
63
views
How to convert NFA with multiple start states to NFA with single start state without epsilon transition?
I can easily convert NFA with multiple start states to NFA with single start state with epsilon transition.
But I want to know how can I do so without epsilon transition
Here's my idea
Suppose s1 and ...
- 1
0
votes
3
answers
8k
views
Is (a+b)* and (ab)* same in finite automata?
Regular language of (a+b)* and (ab)* are:
(a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...}
(ab)* = { ε, a, b, aa, ab, ba, bb, aaa, ... }
I am new to Finite automata and this simple notion is ...
- 7,768
0
votes
1
answer
63
views
Simplifying regex expression (L+M*)*
To simplify it, it seems that we can do $(L+M^*)^* = (L+M)^*$, but I also need to prove it.$(L+M)^* ⊆ (L+M^*)^*$ seems straight forward. However, $(L+M^*)^* ⊆ (L+M)^*$ is what I couldn't figure out. ...
CommunityBot
- 1
3
votes
1
answer
2k
views
Are DFAs unique?
For a given regular is expression, once we construct a deterministic finite automaton: is that automaton unique for that expression? In a sense, that no other DFA (different number of vertices or ...
