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
1
vote
1
answer
38
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 ...
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 &...
CommunityBot
- 1
1
vote
1
answer
138
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
71
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
0
votes
0
answers
16
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
0
votes
2
answers
2k
views
In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?
Let's say I have a string 0110 and after 011 I reach an accept state (let's call the accept state "q") in an NFA. However, there is no transition mentioned in the diagram from q for the ...
CommunityBot
- 1
0
votes
1
answer
219
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
73
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
1
vote
1
answer
190
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
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 ...
CommunityBot
- 1
5
votes
2
answers
315
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 ...
- 38.2k
1
vote
1
answer
53
views
Find a transducer that maps a given deterministic process to another
Let $S$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $\mathcal{A}$ and $n$ hidden states, ...
CommunityBot
- 1
0
votes
1
answer
112
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
0
answers
13
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
36
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 ...
- 38.2k
2
votes
1
answer
62
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 ...
- 38.2k
0
votes
0
answers
22
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
2
answers
4k
views
Exactly what is the difference between Finite Automata and Transition Graphs?
I haven't found a good enough answer by googling. Here's what i know:
TG's can have more than one initial state
In TG's, Edges/transitions can be labelled with strings
In TG's, it is not necessary to ...
0
votes
0
answers
21
views
Complexity of checking equivalence of finite automata [duplicate]
Given two finite automata $M_1,M_2$. I couldn't find the computational complexity of the problem of determining whether $L(M_1) = L(M_2)$.
D.W.♦
- 152k
0
votes
1
answer
24
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-...
D.W.♦
- 152k
2
votes
2
answers
69
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 ...
- 38.2k
1
vote
2
answers
28
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 ...
- 699
0
votes
1
answer
39
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
1
vote
1
answer
86
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 ...
- 29.1k
0
votes
0
answers
33
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. ...
-2
votes
1
answer
340
views
Proving that removing unreachable states from $M$ does not change $L(M)$
What is the idea behind proving that:
Removing unreachable states from a DFA $M$ does not change $L(M)$.
I don't know what cases I need consider. Consider any $w\in \sum^*$ and then check for the ...
- 577
0
votes
0
answers
59
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 ...
- 129
1
vote
2
answers
68
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
3
votes
1
answer
71
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
11
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: ...
0
votes
0
answers
33
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 ...
- 129
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
2
votes
0
answers
197
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
0
votes
0
answers
26
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
0
votes
1
answer
83
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
1
vote
2
answers
84
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) : ...
- 29.1k
1
vote
1
answer
437
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
2
votes
1
answer
90
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 ...
- 29.1k
0
votes
1
answer
351
views
How to construct an NFA Ai for the given Regular property P1 and P2?
Let AP = {a; b; c}.
Consider the following regular safety properties:
(a) P1: If a becomes valid, afterwards b stays valid ad infinitum or until c holds.
(b) P2: Between two neighbouring occurrences ...
CommunityBot
- 1
0
votes
1
answer
67
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
1
answer
65
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
1
vote
1
answer
76
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 ...
- 479
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}...
- 940
1
vote
2
answers
86
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 ...
- 1,225
1
vote
1
answer
78
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.
...
- 4,358
3
votes
1
answer
625
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 ...
- 12k
3
votes
3
answers
283
views
PDA for a language where the second part is not the reverse of the first part
I came across an exercise for constructing a PDA for the following language:
$$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$
Where $L \subseteq ({a,b,c})^*$
So $n$ and $m$ are both a ...
CommunityBot
- 1
0
votes
1
answer
54
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 ...
- 11.4k