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.

learn more… | top users | synonyms

0
votes
1answer
60 views

Model paths by regular languages [on hold]

I want use DFA to describe a sequence of movements in a 2D-space (language will be the path accepted by automaton in a particular case). That is a typical modeling problem: how can I encode a ...
1
vote
1answer
35 views

Converting Regular expression to DFA by building syntax tree

There is a way to convert regular expression to DFA (deterministic finite automata) which is to build a syntax tree and then compute first pos, last pos, follow pos, and then use a Transition ...
0
votes
2answers
43 views

How to get the intersection of two regular languages?

I was trying to figure out the value of the following expression. (0 | 1)*00 ∩ (0 | 1)*01 I tried drawing DFAs for(0 | 1)*00 ...
7
votes
3answers
93 views

Algorithms for minimizing Moore automata

Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times ...
4
votes
4answers
132 views

Does Thompson's algorithm produce optimal NFAs?

I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of ...
0
votes
1answer
23 views

FSM + state data is Turing complete abstraction?

I'm playing with Akka FSM. The declaration of a an Akka FSM consists of states + data mantained during the states (the akka doc is more clear than me) + events that trigger transitions between states. ...
2
votes
1answer
84 views

Is this method of proving non-regularity is equivalent to pumping lemma?

I find it really difficult to prove non-regularity of a language using pumping lemma. I do understand that regular language is the language that can be expressed ...
-1
votes
1answer
45 views

Converting this NFA to Turing Machine

I'm asked to choose a DFA and convert it to NFA and then convert it to Turing machine... I have done the first two parts as follows: DFA: --> NFA: --> Turing machine: ??? I haven't found ...
0
votes
2answers
37 views

Transitions triggered by sets of events

In automata theory books, I always studied examples where a state transition from A to B occurs due to a single event $e$ (say, receiving a particular character). Is it theoretically possible that a ...
0
votes
2answers
110 views

Draw a DFA that accepts ((aa*)*b)*

A homework question asks me to a draw a DFA for the regular expression $((aa^*)^*b)^*$ I'm having trouble with this because I'm not sure how to express the idea of $a$ followed by $0$ or many $a$'s ...
4
votes
1answer
48 views

Who invented the state elimination algorithm for converting finite automata into regular expressions?

The state elimination algorithm is an algorithm for converting finite automata into regular expressions. It's found in many textbooks, including Sipser's Introduction to the Theory of Computation. ...
0
votes
0answers
38 views

extended transition function for NFAs

Below I am using a DFA transition function that is extended to accept words instead of just symbols. Let's say it is given that the following information is true: $$\delta(q_0, 0^3) = \delta(q_0, ...
1
vote
0answers
50 views

Formal language properties and finite state machines [closed]

What are properties of a formal language? Which and how would they be needed to prove that some Non-Deterministic finite state machine can accept a given language?
2
votes
2answers
52 views

DFA which visit a specific state at least once

Given a DFA M that satisfies language A, how do I modify M such that a new language B consisting of all strings that are accepted by M and cause M to enter a specific state r at least once are ...
-1
votes
1answer
54 views

DFA for regular language [closed]

I need to construct a DFA which accepts the following language: $$ L = \{w \in \{a,b\}^{\ast}\mid \#_{a}(w) \bmod 3 = \#_{b}(w) \bmod 2\} $$ I have no clue how to solve this issue. Can you please help ...
0
votes
1answer
72 views

What is the minimal number of states for the DFA?

Let the regular expression $R = ((a^*\cup \emptyset \cup \varepsilon^*)^*b)^*$ above $\Sigma = \{a,b,c,d\}$. What is the minimal number of states for a DFA accepting this regex? $1$ $2$ $4$ $5$ ...
0
votes
1answer
46 views

Handling dead state in NFA to DFA conversion

I want to convert below NFA into DFA: I prepared below tables and finally the NFA: NFA However I feel I am wrong here, since original NFA does not have any transitions defined for state C ...
-2
votes
1answer
81 views

Thompson's Construction Algorithm produces a different NFA

My teacher asked me to convert the regular expression $(a | b)^*$ to an NFA using Thompson's algorithm – well, I'm well aware of how this algorithm works, but since I'm not good at memorising details, ...
1
vote
1answer
37 views

Infinite Memory

It seems to me that any problem whose solution requires finite memory can be emulated on a Finite State Machine . This would make those problems that can't be solved by a Finite State Machine to ...
0
votes
1answer
19 views

RAM Machine and FSM

I heard it's possible to model a bounded-memory RAM as a Finite State Machine. I'm curious about the method of how we would that. Does anyone have a clue ? Thanks in advance
2
votes
1answer
71 views

Can DFA with output (definition?) match expressiveness of NFA with unique output?

For a deterministic finite automaton (DFA), some output tasks are easy when done in one direction, but difficult (or impossible?) when done in the reverse direction. Let's take a simple example of ...
4
votes
1answer
66 views

Language of walks in a grid – context-free?

Consider the infinite two-dimensional grid with integer co-ordinates. A walk in the grid can be represented by a string over the alphabet $\{u,d,l,r\}$, where the letters stand for moving one square ...
3
votes
2answers
69 views

Proving regular languages are closed under a form of interleaving

I've got the following definitions: $$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$ when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means ...
1
vote
2answers
40 views

NFA-style representation of regexps which includes AND

I'm looking for a regexp matching strategy that supports conjunction and which is based on an NFA-style machine. I know how to handle conjunctions using a DFA, or using Brzozowski's approach, but for ...
-2
votes
1answer
105 views

Convert RE to DFA [duplicate]

I've been trying to convert a regular expression to a non-deterministic finite automata (NFA) first using Thompson's construction, giving: , which looks correct. I am then using subset ...
7
votes
2answers
111 views

Minimize Deterministic Finite Automata with no accepting states

I have a finite automaton with no final/accepting states, so F is empty. How do I minimize it? I got this on a test and I didn't know how to approach the problem because the automaton had no ...
5
votes
2answers
33 views

Is relative regularity distinct from regularity?

Let $L$ and $G$ be languages over a finite alphabet $\Sigma$. $L$ is regular relative to $G$ if $L \subseteq G$ and there is a finite automaton that accepts every input in $L$, and rejects every input ...
2
votes
2answers
40 views

Is the question of whether the language of a DFA/CFG is equal to a particular set of string decidable?

Suppose I have a set of strings $S$ that is generated from the alphabet. Suppose I have a DFA $D$ and a CFG $G$, are the questions of $\{D\mid D\text{ is a DFA and }L(D) = S\}$ and $\{G\mid G\text{ ...
-2
votes
2answers
34 views

Creating a FSA using 3 input codes and a parity check digit [closed]

Need help understanding the overall idea behind this scenario, I've got 3 input codes namely: A (0100) B (0010) and C (0001) and i'm supposed to have a odd parity of 0's. I've started making a machine ...
0
votes
0answers
14 views

Effect of mismatches on string matching finite automata

I am contemplating a string matching FA algorithm (not KMP). The complexity of its transition function calculation ie the preprocessing is m(length of pattern )* (the language of the FA) . What effect ...
2
votes
0answers
59 views

How does a minimal DFA ensure minimal computational cost?

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence: The minimal DFA ensures minimal computational cost for tasks such as pattern matching. ...
0
votes
1answer
39 views

NFA not accepting a certain string

I am trying to make a non-deterministic NFA that does not contain a string "101". How do I make my NFA so that it does not have this string? My attempt:
1
vote
0answers
83 views

If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$

I am interested in proving that if $\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 ...
3
votes
1answer
85 views

Product of a Transition System and a Finite Automaton

Dealing with a question that asks me to compute the product of the following transition system and finite automaton Can't seem to find a good example on how to do this so I sort of just freestyled ...
2
votes
2answers
130 views

show that language $L'$ is regular (given $L$ regular)

I am working on the following question: $L$ is regular. Show that $L'=\{x|\exists y,z,\ xyz\in L\wedge |x|=|y|=|z|\} $ is also regular. Firstly I show my idea. When you accept it I will try to ...
1
vote
0answers
64 views

How to draw a clearly arranged DFA of a language with modulo rules?

I know how to draw a DFA, but I have problems with this specific one: ${L = \{ w \in \{a,b,c\}^* \mid \ |w|_a \equiv |w|_b - 2|w|_c \mod \ 5 \} }$ This language is regular and there has to exist a ...
1
vote
1answer
56 views

Feynman finite state machine

In his lectures on computer science, Feynman talks about finite state machines: he present a simple delay finite state machine Let me now give a specific example of an FSM that actually does ...
0
votes
1answer
53 views

DFA Minimization

I am currently in a class that deals with DFA's and their minimization. However I believe I have reached a DFA where the method of minimization we were taught doesn't work. I have the following DFA ...
0
votes
2answers
53 views

Converting regular (Type-3) grammar to a deterministic finite state automaton

I would like to create a deterministic finite state automaton (DFA) M=(Q, Σ, δ, q0, F) that is accepting the language generated by the following regular grammar (RG) G=(N, Σ, P, S). In short I want to ...
6
votes
1answer
198 views

What is the relationship between Turing Machines with a finite tape and Finite State Automata?

I seem to recall from an undergraduate class that for a Turing Machine with a finite tape there will always exist a corresponding Finite State Automata, but I've been unable to find this confirmed ...
-2
votes
1answer
38 views

Why is this sequence not acceptable for this DFA?

Why is the sequence 1100101 not acceptable for this DFA? Is it because once it reaches the final state 'q3' it can't go back to 'q1'?
6
votes
3answers
213 views

How to create DFA from regular expression without using NFA?

Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that? I asked this question to our professor but he ...
1
vote
2answers
69 views

Prove correctness of DFA ending with ab

I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{a,b\}^*\}$ I know that I need to prove by induction ...
0
votes
1answer
50 views

DFA that recognizes 0 in every odd position

I had a question that asked for the DFA that accepts the following language: {w | every odd position of w is a 0 } Should this DFA accept the empty string, since ...
-2
votes
1answer
40 views

Constructing Epsilon-closures

I am recently learning about automaton and I was confused at an exercise that was given to me. In the lecture, we were given this exercise: Given a FA with transitions $$\begin{array}{c|ccc} ...
2
votes
2answers
69 views

Are device drivers state machines?

I know that device drivers are attached to device controllers, which have their own registers and some local buffer storage. I'm wondering if I can think of device drivers as little state machines -- ...
0
votes
1answer
42 views

Prove that Language is not Regular using closure(s)

I'm having a really tough time trying to comprehend proofs via closure and pumping lemma. None of the examples I can find are similar to the one's im looking to prove. Can anyone explain if I'm ...
1
vote
0answers
24 views

Number of states of finite automata [duplicate]

Prove that for each $n>0$, a language $L_n$ exists where $L_n$ is recognizable by an NFA that has $n$ states, and If $L_n=K_1 \cup \dots \cup K_k$, for regular languages $K_i$, then at least ...
-2
votes
1answer
56 views

How can I build a DFA for ${a^m b a^n | m+n \equiv 1 mod 3}$? [duplicate]

I have a language $\{a^m b a^n | m+n \equiv 1 mod 3\}$ $m+n$ can be 1, 4, 7, 10, 13, 16, 19, 22, ... $m+n$ is the number of all $a$'s in the word How can I build a DFA for this language?
0
votes
0answers
20 views

Representing lookbehind and lookahead in FSMs based off regexes [duplicate]

As part of an assignment, I have to write regexes matching lists of rules and then make state machines representing those regexes. Heavy use of negative lookbehinds and lookaheads is essential in one ...