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
189
views
Finite State Automata for recognising consecutive characters
I'm currently working on this question as part of some homework, it has me stumped.
I'm familiar with finite state automata (FSA), I know how they work and I've read everything I can find on Google, ...
- 155
1
vote
2
answers
3k
views
Language acceptance by DFA
I have some questions regarding acceptance of a language by DFA
Whether more that one dfa accept a language
Whether a dfa can accept more than one language
- 2,171
8
votes
3
answers
1k
views
Proving the language which consists of all strings in some language is the same length as some string in another language is regular
So I've been scratching my head over this problem for a couple of days now. Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose ...
- 81
2
votes
1
answer
3k
views
Simplification of regular expression and conversion into finite automata
This is a beginners question. I and reading the book "Introduction to Computer Theory" by Daniel Cohen. But I end up with confusion regarding simplification of regular expressions and finite automata. ...
- 205
2
votes
1
answer
897
views
Runtime of the binary-GCD state machine
I am doing self study from MIT OCW exercises and I could not understand this question.
The following rules define the binary-GCD state machine working on states in $\mathbb{N}^3$ with start state $(...
- 21
3
votes
2
answers
2k
views
If $L$ is a regular language, how to prove $L_1 = \{ uv \mid u \in L, |v| =2 \}$ is also regular?
If $L$ is a regular language, prove that the language
$L_1 = \{ uv \mid u \in L, |v| =2 \}$
is also regular.
My idea: $L$ can be represented as a DFA and then you could add 2 consecutive ...
- 133
9
votes
1
answer
538
views
Problem with implementing Brzozowski's algorithm
I've been trying to implement Brzozowski's algorithm but I've just discovered that it creates suboptimal automata for a certain class of inputs, having one more state than what is really needed in the ...
- 193
1
vote
2
answers
227
views
How to make NFA remember its first step?
I have to design an NFA that will take the strings "token" and token.
I can use $\lambda$ or ...
- 11
3
votes
3
answers
4k
views
Finding an isomorphism between finite automata
Im having trouble figuring out how to determine if two finite automata are the same apart from renumbered states.
More specifically, heres an example:
It's easy to generate a regular expression ...
user3115
0
votes
1
answer
683
views
Program that generates a regular expression from an FA [duplicate]
Possible Duplicate:
How to convert finite automata to regular expressions?
Im curious if anyone knows if its possible to write a program to generate a regular expression given a finite automation....
user3115
5
votes
1
answer
3k
views
Prove that the language of non-prime numbers written in unary is not regular
Im trying to prove that the following language is not regular.
$$\text{Notprime} = \{a^n \text{where \(n\) isn't prime}\}
= \{\epsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots\}$$
Heres what I have:
"If ...
user3115
2
votes
1
answer
140
views
Describing Strings
Im trying to figure out how to describe fifty-six strings to test if a three state FA over the alphabet $\{a,b\}$ has a finite language.
The number fifty-six comes from a theorem that states if a ...
user3115
20
votes
1
answer
17k
views
How do I write a proof using induction on the length of the input string?
In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however ...
- 303
1
vote
1
answer
4k
views
How do you prove that two languages are equivalent?
How can you show that the Language accepted by an NFA and the reverse NFA is the same?
For a language $L$, there is an $L^R=\{ w^R \mid w \in L\}$
Let's say that $w^R$ is the string obtained by ...
- 11
7
votes
3
answers
887
views
What piece am I missing to turn this idea into a programming language?
I've been doing some reading (I'll name drop along the way) and have selected a few scattered ideas that I think could be cobbled together into a nifty esoteric programming language. But I'm having ...
- 277
23
votes
3
answers
7k
views
How to prove that DFAs from NFAs can have exponential number of states?
All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. ...
- 397
0
votes
1
answer
779
views
Why isn't converting from an NFA to a DFA working?
I am just beginning to learn computation theory. I wrote up a non-deterministic finite automata that accepts strings that contain the substring "abba":
I tried to convert it to a DFA by putting ...
- 397
3
votes
2
answers
186
views
Compute 'insertable' letters in a regular language
Let $L$ a regular language and define the subsequence closure of $L$ as
$\qquad \displaystyle S(L) = \{ w \mid \exists w' \in L.\ w \text{ subsequence of } w'\}$.
The problem I want to solve is to ...
- 161
3
votes
1
answer
1k
views
What is the purpose of k in the transitive closure method?
When converting a DFA to a regular expression using the transitive closure method, what is the significance of state $k$ and what values $k$ takes? If $k$ represents the intermediate states then what ...
- 31
12
votes
4
answers
6k
views
NFA with exponential number of states when determinized
How can I build an example of a regular language where the minimal DFA has $2^n$ states and the minimal NFA has $n$ states? Obviously the DFA's state-set should contain all subsets of the the NFA's ...
- 3,650
2
votes
3
answers
3k
views
NFA for binary words that do not end in 10
Construct an NFA over $\{0, 1\}$ whose language contains only words that do not end with $10$.
This is one of the first problems in the book, so it's supposedly easy. I just can't figure it out. It's ...
user10537
3
votes
2
answers
4k
views
Pumping Lemma for regular language for $a^n$ where $n$ is even fails
$$L=\{a^n \mid \text{\(n\) is even}\}$$
This is regular but fails in the pumping Lemma.
Assuming $m=4$, $w=aaaaaa$, $|w|=6$ (even).
Let $w=xyz$,
$x=a$,
$y=aaa$.
We have $|y|>0$ and $|xy| \le m$.
...
Raj
31
votes
4
answers
100k
views
How to show that a "reversed" regular language is regular
I'm stuck on the following question:
"Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{...
- 313
6
votes
2
answers
10k
views
Cost in time of constructing and running an NFA vs DFA for a given regex
Repost from Stack Overflow:
I'm going through past exams and keep coming across questions that I can't find an answer for in textbooks or on google, so any help would be much appreciated.
The ...
- 79
5
votes
1
answer
628
views
Is the set of minimal DFA decidable?
Let $\mathrm{MIN}_{\mathrm{DFA}}$ collection of all the codings of DFAs such that they are minimal regarding their states number. I mean if $\langle A \rangle \in \mathrm{MIN}_{\mathrm{DFA}}$ then for ...
- 511
2
votes
2
answers
616
views
Counting with constant space bounded TMs
The problem, coming from an interview question, is:
You have a stream of incoming numbers in range 0 to 60000 and you have
a function which will take a number from that range and return the
...
- 1,198
0
votes
1
answer
722
views
Does this regular expression equal this automata?
I just came across an exercise which is to find a regular expression for the following automata, such that the regular expression and the automata generate the same language.
One solution presents ...
- 171
2
votes
1
answer
889
views
LTS of this simple FSP
I have this finite-state process with the corresponding labeled transition system:
The FSP is:
...
- 233
6
votes
1
answer
633
views
Building a finite state transducer
I know it's possible to build a Finite State Transducer for converting numbers from base 2 to base 4 or 8 or other powers of 2 (translating from base N to base N^M is easy). However I've never seen a ...
- 163
5
votes
3
answers
531
views
Is the set of codes of Deterministic Finite-State Automata a regular language?
Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
- 61
31
votes
4
answers
6k
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 ...
- 435
0
votes
2
answers
3k
views
Are supersets of non-regular languages also non-regular?
I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid?
Since $L_1$ is not regular, there does not exists a finite automata $M_1$ ...
- 129
2
votes
1
answer
1k
views
Automata that recognizes Kleene closure of permutations of three symbols
This is an automata theory homework question.
I need to create DFA that meets the following criteria:
Alphabet $\Sigma = \{ a, b, c \}$
Machine accepts empty string and strings of length that is a ...
- 461
10
votes
2
answers
569
views
Optimal myopic maze solver
I was fooling around with Google Blocky's Maze demo, and remembered the old rule that if you want to solve a maze, just keep your left hand to the wall. This works for any simple-connected maze and ...
- 4,792
-1
votes
1
answer
312
views
construct regular expression
I need help with the following exercise:
Construct an $\varepsilon$-NFA for the following regular expression $(a|\varepsilon)(ba)^*(c^*a|bc)^*$.
i already tried this exercise with nerode but i didnt ...
137
votes
4
answers
201k
views
How to convert finite automata to regular expressions?
Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
- 71.8k
8
votes
1
answer
9k
views
Prove that regular languages are closed under the cycle operator
I've got in a few days an exam and have problems to solve this task.
Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation
$\operatorname{cycle}(L) = \{ xy \mid x,y\in \...
- 511
4
votes
1
answer
1k
views
Transforming an NFA into an NFA of similar size but without $\epsilon$-transitions
I'm learning for the exam and have problems with this task:
Describe an algorithm that transforms a given NFA $A = (Q, \Sigma, \delta, q_0, F)$ (which may have $\epsilon$-transitions) into an ...
10
votes
3
answers
3k
views
If $L$ is context-free and $R$ is regular, then $L / R$ is context-free?
I'm am stuck solving the next exercise:
Argue that if $L$ is context-free and $R$ is regular, then $L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} $ (i.e. the right quotient) is context-...
- 201
17
votes
3
answers
7k
views
Brzozowski's algorithm for DFA minimization
Brzozowski's DFA minimization algorithm builds a minimal DFA for DFA $G$ by:
reversing all the edges in $G$, making the initial state an accept state, and the accept states initial, to get an NFA $N&#...
- 4,792
32
votes
2
answers
3k
views
Why is a regular language called 'regular'?
I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata.
He defines a regular language as anything ...
- 883
1
vote
1
answer
552
views
Non-regular Languages? [duplicate]
Possible Duplicate:
How to prove that a language is not regular?
Why $L_a$ and $L_b$ are not reguluar?
$L_a = \{ e^i f^{n-i} g^j h^{n-j} : n \in N, 1 \leq i, j \leq n \}$.
$L_b= \{nm^{i_1} ...
- 879
5
votes
2
answers
368
views
DFA with limited states
Lets $L_z \ := \{ a^i b^i c^i : 0 \leq i < z \}$
$\{a,b,c\} \in \sum^*$
there is a DFA with $\frac{z(z+1)}{2}+1$ states - How can I prove this?
And I need largest possible number $n_z$, for ...
- 879
9
votes
1
answer
2k
views
Connection between KMP prefix function and string matching automaton
Let $A_P = (Q,\Sigma,\delta,0,\{m\})$ the string matching automaton for pattern $P \in \Sigma^m$, that is
$Q = \{0,1,\dots,m\}$
$\delta(q,a) = \sigma_P(P_{0,q}\cdot a)$ for all $q\in Q$ and $a\in \...
- 93
10
votes
4
answers
2k
views
Words that have the same right- and left-associative product
I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting:
Give a non deterministic finite automaton accepting ...
12
votes
3
answers
1k
views
How to convert an NFA with overlapping cycles into a regular expression?
If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as ...
- 374
5
votes
4
answers
7k
views
A DFA for recognizing comments
The following DFA is a lexical analyzer which is supposed to recognize comments. The lexical analyzer will ignore the comment and goes back to the state one. I'm told that there's something wrong with ...
- 2,173
19
votes
3
answers
443
views
Is this language defined using twin primes regular?
Let
$\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}.$
Is $L$ regular?
This question looked suspicious at the first glance and I've realized that it is connected with the ...
- 2,157
16
votes
2
answers
570
views
Languages accepted by modified versions of finite automata
A deterministic finite automaton (DFA) is a state machine model capable of accepting all and only regular languages. DFAs can be (and usually are) defined in such a way that each state must provide ...
- 12.7k
17
votes
3
answers
3k
views
What are the possible sets of word lengths in a regular language?
Given a language $L$, define the length set of $L$ as the set of lengths of words in $L$:
$$\mathrm{LS}(L) = \{|u| \mid u \in L \}$$
Which sets of integers can be the length set of a regular language?...
