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,717
questions
0
votes
0
answers
29
views
Can someone explain the following NFA?
I'm learning NFA and the following question is confusing me.
Can Someone explain the answer. I have a feeling that it might be wrong.
Thank you!
-1
votes
2
answers
112
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 ...
- 11
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?
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
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 ...
0
votes
0
answers
71
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
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
68
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 ...
0
votes
1
answer
62
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 ...
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 ...
- 11
0
votes
0
answers
46
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
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
49
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
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
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
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 ...
- 101
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, ...
- 141
0
votes
0
answers
66
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
2
answers
109
views
What can i say about L1 given that L2, L1L2 and L2L1 are regular?
I found this question in one of our past exams, and I'm not to sure about the correct answer.
I have a language L1 (which i don't know anything about) and another language L2, which is regular, the ...
- 11
-4
votes
1
answer
54
views
For each of the following languages, give a regular expression over {a, b}
$\{a^{2n}b^{n+k+1}a^k ∈ \{a, b\}^∗ \mid n \ge 0, k \ge 0\}$
0
votes
3
answers
74
views
How to create a DFA with memory
How can I create a DFA that has memory such that I could write a rule for this DFA that states ...
0
votes
1
answer
56
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}
- 1
1
vote
1
answer
49
views
Does graph traversal require stack machine?
I'm writing a graph traversal function to be used in a garbage collector.
To avoid stack overflow, I used a finite state machine. Roughly, it descends into child nodes recursively to mark objects, and ...
- 192
0
votes
1
answer
140
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 ...
- 1
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 ...
- 23
1
vote
1
answer
20
views
Meaning/veracity of "each state has [..] or two outgoing ϵ transitions" in Thompson's construction
The dragon book lists properties of an NFA N(r) created using Thompson's construction, in particular:
Each state of N(r) other than the accepting state has either one outgoing transition on a symbol ...
1
vote
0
answers
54
views
Regex to DFA - How do I implement parsing preferences in regex search?
I've tried a to implement a Regex to DFA converter, and it works, so far, but I don't understand how to implement "parsing preferences" in the DFA.
A classic example is $a^*$. This regex is ...
- 111
0
votes
0
answers
163
views
Real-life applications of pure Mealy machines
I'm currently studying formal methods in software engineering related to state machines, specifically Mealy machines. This made me wonder how relevant Mealy machines really are for practical ...
- 161
2
votes
1
answer
69
views
Finite State Machine without recursion
I have found utility in state machines that do not have the complexity of recursion: no self or ancestral transitions.
Is there a name for this sub-category of FSMs? Are they commonly used or ...
- 123
0
votes
0
answers
20
views
Theory of computation
I am trying to look answer for this question of toc please help me find the answer.
The question is :
Construct epsilon NFA(Non deterministic finite automata) for regular expression (0+1)*1(0+1)
- 1
5
votes
2
answers
371
views
Creating a deterministic finite automaton for strings of 2k ones and 3q zeros or a general language
I was requested to draw the graph of a finite state machine whose language is
$$L = \{ w \in \{0, 1\}: w \text{ has $2k$ ones and $3q$ zeros }\}$$
In other words, the number of ones must be even and ...
- 181
0
votes
0
answers
50
views
Right-regular grammar conversion to NFA: production rule with only one variable on right side
I'm trying to convert a right regular grammar to an NFA.
I understand that I need to create a state for every variable and add transitions according to the production rules.
But what if there is a ...
1
vote
1
answer
40
views
Counting States in the trim automaton for $\cup_{i=1}^{p} L_i \circ L'_i$
Preliminaries. Let $n,m,i,j,p,c \in \mathbb{N}$ with $n,m,i,j,p,c \geq 1$.
Let our alphabet be $\{0,1\}$, with
non-empty languages $ L_i \subseteq \Sigma^n$ and $ L'_i \subseteq \Sigma^m$.
The other ...
- 923
0
votes
0
answers
80
views
ALL-NFA is PSPACE-complete
Show that $ALL-NFA$ = {$\langle M\rangle : M$ is $NFA$ and $L(M) = \Sigma^*$} is $PSPACE-complete$.
I've manged o prove that it is $PSPACE$.
It is easy to see that $\overline{ALL-NFA}\in NPSPACE$ (TM ...
- 1
2
votes
1
answer
105
views
Does my finite state automaton accept a string iff it contains the given string as a substring?
I am trying to write down the generalized form of the finite automata which accept strings which contain as a substring an arbitrary string. Here is what I have come up with — I was hoping someone ...
- 125
0
votes
1
answer
30
views
Counting States in the trim automaton for $(L_1 \cup L_2 \cup \ldots \cup L_p) \circ L'$
Preliminaries. Let $n,m,p \in \mathbb{N}$ with $n,m,p > 1$. We allow that $p$
could be large but still bounded by a function of $n$: $p = O(2^n)$. Let our alphabet be $\Sigma = \{0,1\}$, with
non-...
- 923
2
votes
2
answers
77
views
Counting States in the trim automaton for $L\circ L'$
Preliminaries. Let $n,m \in \mathbb{N}$. Let our alphabet be $\Sigma = \{0,1\}$, with non-empty languages $ L \subseteq \Sigma^n$ and $ L' \subseteq \Sigma^m$. We follow the standard definition for ...
- 923
1
vote
1
answer
143
views
Product Construction for DFAs with different alphabets
How would you modify the Product Construction for DFAs to find a DFA that recognises the union of two regular languages with different alphabets. I am not looking for a way of finding an NFA then ...
- 23
0
votes
0
answers
72
views
Help with converting the DFA to a regular expression using Ardens theorem
Can someone explain to me how to convert this DFA to a regular expression? I have tried using Arden’s theorem but I don’t know how to simplify the equations to get the regular expression for this DFA. ...
0
votes
0
answers
123
views
Proving a certain language is regular by constructing a DFA
Let $L$ be a regular language over the alphabet $\sum$, prove that the language defined by $\hat{L} = \{uv \in \sum^* | u^Rv \in L \}$ is regular.
There is guidance in the exercise that instructs us ...
- 229
0
votes
0
answers
16
views
How can I describe an FSA where one or more inputs generate outputs but do not cause transitions?
I have been asked to describe through an FSA a system where some inputs do not determine any state transitions, but that provide outputs. There is no self-transition, and the input is not rejected: ...
3
votes
1
answer
110
views
Brzozowski's algorithm for Kleene star NFA
I have some troubles in understanding of the Brzozowski's algorithm for NFA to minimized DFA transformation. Or maybe I'm doing a mistake in the NFA to DFA transformation steps.
The Algorithm, as ...
- 171
0
votes
0
answers
43
views
Desgining NFA under certain constraints
I've got homework to design NFA to accept a set of strings over {a,b,c} in which each string of the language satisfies: "cac" is a substring and "cc" is not a substring and the ...
- 229
0
votes
0
answers
78
views
How to prove (L+M)* = M*.(L.M*)*
Question is to simplify (LM*)* and I couldn't figure out a way to simplify it. Since (L+M)* = M*.(L.M*)*, I guess we can say that it cannot be simplified more. So how do we prove that they are the ...
- 67
1
vote
2
answers
29
views
Confusion with Execution of NDFA
I do not understand the "execution graph" (I think that's what it's called) of the following Non-Deterministic Finite Automata, given on pg 48-49 of Sipser's Intro to TCS (3rd edition):
And ...
- 113
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. ...
- 67
1
vote
2
answers
130
views
Prove a language created by applying a function on a regular language is regular
Let $L$ be a language over $\Sigma=$ {$a,b,c$}
We define $\forall w\in \Sigma ^{*}$ the function $T$ s.t. $T(w)$ is the word we recieve after removing all instances of $a$ in $w$.
Let $T(L)=${$ T(w) : ...
- 315
2
votes
1
answer
104
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 ...
- 67