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
2answers
31 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 ...
0
votes
0answers
19 views

time complexity of subset construction for determinization in term of size of given automata [on hold]

For a given non-deterministic finite automata $M$ of size $n$ I think the subset construction for automata determinization is $\mathcal{O}(2^n\cdot n^2 )$ for constant input alphabet size. That is ...
7
votes
3answers
77 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
3answers
104 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 ...
-2
votes
0answers
24 views

Finite State Automata construction problem [duplicate]

Can anybody explain me how to construct deterministic finite automata for these languages: $L = \{ xwx^R \mid x, w \in \{a,b\}^+ \}$ where $x^R$ is the reverse of string $x$. $L = \{ (1^k)y \mid y = ...
0
votes
1answer
19 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
83 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
0answers
19 views

Transition table for intersection of two languages

Ok, so I am building a transition table for the intersection of two languages, and I understand that I get $z_1$ from the starting point of both $x_1$ and $y_1$, then from there $z_2$ can consist of ...
-1
votes
1answer
43 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
96 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
44 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
33 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
45 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
51 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
50 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
52 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
35 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
72 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
36 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
15 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
66 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
62 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
66 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
90 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
102 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
32 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
13 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
36 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
81 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
77 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
1answer
104 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
60 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
54 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
50 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
49 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
188 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 ...
-3
votes
1answer
36 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'?
5
votes
3answers
186 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
66 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
42 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
36 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
66 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
55 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?