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.

Filter by
Sorted by
Tagged with
2
votes
1answer
552 views

Does this DFA have a solution?

I am trying to create a DFA that can recognize strings with alphabet $\{a,b,c\}$ where $a$ and $c$ appear even number of times and where $b$ appears odd number of times. I am wondering that this may ...
3
votes
2answers
497 views

Proving regularity via equivalence classes

Given two regular languages $L_1$ and $L_2$, we define a new language $$L=\{w_1w_2\mid \text{ there exist two words } x,y \text{ such that } xw_1\in L_1, w_2y\in L2\}$$ How do I show that $L$ is ...
3
votes
1answer
11k views

Finite state automata, multiple completion states?

I'm currently studying for an exam for a course where some of the material covered included finite state automata, I've completed a question and I'm not sure about my answer. Exercise Explain what ...
8
votes
2answers
14k views

Is this intersection of DFAs correct?

I'm constructing a deterministic finite automata (DFA) for a language of all strings defined over $\{0,1\}$ whose length is even and number of $1$s is odd. I constructed each DFA separately and then ...
1
vote
1answer
147 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, ...
1
vote
2answers
2k 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
8
votes
3answers
512 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 ...
2
votes
1answer
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. ...
2
votes
1answer
690 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 $(...
3
votes
1answer
800 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 ...
8
votes
1answer
395 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 ...
1
vote
2answers
143 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 ...
3
votes
3answers
3k 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 ...
0
votes
1answer
629 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....
5
votes
1answer
2k 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 ...
2
votes
1answer
137 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 ...
20
votes
1answer
15k 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 ...
1
vote
1answer
3k 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 ...
7
votes
3answers
832 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 ...
21
votes
3answers
5k 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. ...
0
votes
1answer
672 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 ...
3
votes
2answers
178 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 ...
3
votes
1answer
935 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 ...
11
votes
4answers
5k views

NFA with exponential number of states when deteminized

How can I build an example of a DFA that has $2^n$ states where the equivalent NFA has $n$ states. Obviously the DFA's state-set should contain all subsets of the the NFA's state-set, but I don't know ...
2
votes
3answers
2k 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 ...
2
votes
2answers
3k 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$. ...
23
votes
4answers
69k 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^{...
6
votes
2answers
8k 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 ...
5
votes
1answer
363 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 ...
2
votes
2answers
538 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 ...
0
votes
1answer
599 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 ...
2
votes
1answer
744 views

LTS of this simple FSP

I have this finite-state process with the corresponding labeled transition system: The FSP is: ...
5
votes
1answer
495 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 ...
5
votes
3answers
359 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 ...
28
votes
4answers
4k 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 ...
0
votes
2answers
2k 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$ ...
2
votes
1answer
957 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 ...
10
votes
2answers
518 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 ...
-1
votes
1answer
291 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 ...
125
votes
4answers
174k 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 ...
8
votes
1answer
7k 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 \...
4
votes
1answer
962 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
3answers
2k 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-...
16
votes
3answers
6k 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&#...
31
votes
2answers
2k 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 ...
1
vote
1answer
446 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} ...
4
votes
2answers
341 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 ...
7
votes
1answer
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 \...
9
votes
4answers
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 ...
11
votes
3answers
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 ...