Questions about mathematical devices that read an input stream symbol by symbol and use a state transition map to produce an output stream, maybe using secondary storage.

learn more… | top users | synonyms

5
votes
3answers
186 views

Relationship of algorithm complexity and automata class

I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), ...
3
votes
1answer
37 views

What is the origin of using Q to denote a set of states in an automaton?

When talking about DFAs and NFAs as 5-tuples, it's common to use the letter $Q$ to denote the set of states in the automaton and to denote individual states with names like $q_0$, $q_1$, etc. Is ...
2
votes
1answer
49 views

How can I draw a Moore diagram for a given circuit?

I have a circuit and I should draw a moore diagram (state diagram) for that. ​ The problem is that every state can have 5 inputs and this makes the question hard for me. ​ I tried about 20 times to ...
11
votes
1answer
2k views

Can a language have more than one DFA?

For Example when we consider a DFA that allows the strings having neither sub strings 00 or 11 I can produce the following two ...
1
vote
1answer
30 views

Regex to NFA to complement

So I've found out that a regular expression $n$ symbols long converts to an NFA with $O(n)$ states, it is linear. Now to go from that NFA to the complement of the NFA, since I can't just flip accept ...
-1
votes
0answers
42 views

regular Language and nfa [on hold]

please how to proof this proposition can you give me a way to a proof : let L be a regular language that does not contain epsilon.show that there is an nfa without epsilon-transitions and with a ...
0
votes
1answer
37 views

complement of a language-nfa

hi i know that the question 5 is true because by definition w ∈ L if and only if δ*(q0,w)∩F ≠ ∅. Consequently, if δ∗ (q0,w)∩F = ∅, then w ∈ L1. "L1 is the complement of L" but iam really confused ...
0
votes
1answer
44 views

Flipping accept states DFA vs. NFA [duplicate]

I realized that if a language L is recognized by a DFA, then flipping its accept and reject states (aka switching all the accept to reject states and all the reject states to accept) works to ...
3
votes
1answer
32 views

How Can I Recognize When to Use ε-Transitions in an NFA?

I am learning about finite automata for the first time. I am having trouble understanding the purpose of ε-transitions in an NFA, which seem to be crucial to counting the number of states in an NFA ...
1
vote
2answers
28 views

Techniques to create a PDA for a language that is the conjunction of two languages

When I was working with finite automata, I figured out that we can put together two FA two build a new one that is the intersection between the two. This is possible because regular languages are ...
1
vote
2answers
76 views

Designing a DFA for binary strings having 1 as the fourth character from the end

I came across someone else's old post here Designing a DFA that accepts strings such that nth character from last satisfies condition And decided to try it. Apparently it was a homework problem but ...
0
votes
2answers
29 views

In this example of determinising an NFA, isn't there an edge missing in the result?

I am reading a computer theory book and came across the following example converting a NFA to a DFA: My question is, would you not need an edge labeled $b$ going from the $x_4$ node on the right to ...
3
votes
0answers
49 views

Proof $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic

Without using pumping lemma for deterministic context-free languages I need to prove that the language $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic. Someone ...
7
votes
3answers
136 views

DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$

We can form DFA accepting binary numbers divisible by $n$. For example DFA accepting binary numbers divisible by 2 can be formed as follows: Similarly DFA accepting binary numbers divisible by 3 ...
3
votes
2answers
64 views

Determining states in a DFA

In computational theory for deterministic finite automata, there is a 5-tuple representation containing $Q$, $\Sigma$, $\Delta$, $Q_0$ and $F$. I am wondering how one understands thinking about the ...
0
votes
0answers
24 views

Understanding the construction of states in a deterministic finite automata? [closed]

I'm learning about the construction of DFA's in computational theory and confused as to how I know how many states a DFA should have. In the following example, the question states as followed: ...
3
votes
1answer
48 views

Does a DFA accept an empty string if $q_0$ is the accept state?

Suppose $q_0$ is the start state, does this mean that if it's the accept state, then the machine must accept the empty string since it cannot have a transition with the empty string?
1
vote
1answer
40 views

why DFA to regex by two different methods differ

I was learning converting DFA to regex. I came across Arden's method which solve given DFA as follows: Ardens method Let us form the equations $q_1 = q_10 + q_30 + є$ $q_2 = q_11 + q_21 + q_31$ ...
1
vote
3answers
68 views

DFA for w|w has a length multiple of 2 or 3 [duplicate]

I am trying to create a DFA and a regex for this kind of exercise: $A = \{w ∈ \{0, 1\}^* |\text{length of w is a multiple of 2 or 3}\}$. I tried to do one for $2$ and one for $3$ and then combine ...
1
vote
0answers
22 views

What is the precise mathematical definition of n-iterated recusion?

Primitive recursion can be extended to double-recursion as in the following link: http://www.andrew.cmu.edu/user/kk3n/recursionclass/1primrec.html How can this be generalized to n-iterated ...
1
vote
1answer
96 views

What does the term “Finite” stands for in Finite State Machines?

Do we consider Pushdown Automata, Turing Machines in Finite State Machines? If we don't, then what does the term "Finite" stands for in Finite state machines, as PDAs & TMs are also defined to ...
2
votes
0answers
47 views

A string that takes a DFA from any state to a given state?

EDIT: as templatetypedef commented, this problem is to find out if a DFA has a synchronizing word (a.k.a. "reset sequence"). Given a finite state set $Q$, a finite alphabet $\Sigma$, and a transition ...
2
votes
1answer
47 views

Why is this NPDA?

I am studying PDA at the moment, and I came up with this question. The figure above tells me that although both PDA accept the same language, one is non-deterministic and the other is ...
-2
votes
1answer
43 views

DFA: Why is the transition function not a set? [closed]

The DFA is a 5-tuple ($Q,\sum, \delta, q_0, F$) where -finite set of states ($Q$) -finite set of symbols called the alphabet ($\sum$) -a transition function ($\delta: Q \times \sum \rightarrow Q$) ...
3
votes
1answer
30 views

Problem on finite state machines in the feynman textbook

I'm currently reading Feynman Lectures on Computation and got stuck in problem 3.1 which says Suppose we feed a sequence of 1's and 0's - a binary number - into a machine. Design a machine which ...
-2
votes
1answer
45 views

Automata vs Earley parsing? [closed]

If the language is implementable as mere DFA (i.e. it's a regular language), then why would one need a parsing algorithm such as Earley. Regular languages are a subset of context-free languages, but ...
3
votes
2answers
191 views

How does the NFA decide in a state where there are multiple equally valid “next states”?

How does the NFA decide in a state where there are multiple equally valid "next states"? Such as here: How does it decide on which state it takes to with 1?
0
votes
1answer
33 views

Why not just use FSTs for combining syntactic and semantic analysis?

I've just found the finite state transducer. Since the FST processes two tapes: one for input, one for output, shouldn't it be possible to use FST to "pack together" some compiler stages, such as ...
2
votes
1answer
81 views

What is a weighted or probabilistic automaton?

I'm developing a program that has some entities (things) that are "classified" according to "relevancy". Sort of like search engine (think PageRank). Therefore, I'm looking to implement an automaton, ...
4
votes
2answers
62 views

How is $\emptyset^* = \epsilon$?

I know that $\emptyset$ is a an empty language, i.e. language containing no string. A law involving empty language is: $\emptyset L = L\emptyset = \emptyset$ It correctly states that we cannot ...
-1
votes
1answer
59 views

Is a Pushdown Automata possible for this language?

PDA for a Language L = { $a^i b^j \mid i \neq 2j+1 \}$ over the Alphabet $\Sigma = \{a,b\}$ If it can be constructed, how? Edit : I've tried make the PDA for $$L = \{ a^i b^j \mid i = 2j+1 \}$$ ...
0
votes
1answer
92 views

Proving that two sets of strings are equal

I am stucked at this problem: Let $A=(\Sigma, Q, q_1, F, \delta)$ be a finite deterministic automaton (I.e. $\delta:Q\times\Sigma\to Q$) such that $Q=\{q_1,...,q_m\}$. Let's define foreach ...
9
votes
3answers
411 views

How do I verify that a DFA is equivalent to a NFA?

I'm learning how to convert NFAs to DFAs and I want to make sure I'm doing it right. Obviously, going back in the other direction isn't a thing. Does anyone know of an algorithm to check that a DFA is ...
0
votes
0answers
36 views

confirmation of pushdown automata questions

I have the following questions below that I have gotten from a practice paper but have no answers for them. I have completed them but am not sure if they are right, If anyone could confirm whether ...
0
votes
1answer
73 views

non-deterministic finite automaton state transition table language question

I have the nfa problem below which I dont quite understand. I have been reading many slides on this but I'm having a really hard time understanding them enough to be able to complete the question. I ...
0
votes
3answers
85 views

Why is $\{1^n \mid n > 1\}$ regular?

Given the definition of a regular language is one that can be expressed with finite memory, how is $\{1^n \mid n \geq 1\}$ regular? The $n$ is unbounded. I know a DFA can be drawn, which means the ...
-1
votes
1answer
31 views

Algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A_1)$ and $y\in L(A_2)$

Let $A_1=(Q,\Sigma,q_0,F_1,\delta _1)$ and $A_2=(P,\Sigma ,p_0,F_2,\delta _2)$ a finite non determinustic automaons. Describe algorithm that deside if there are two words $x$ and $y$ in the same ...
0
votes
0answers
30 views

Why is this TM only as powerful as a DFA? [duplicate]

Supposing if we restrict the Turing Machine (with single tape) to not write on portion of tape with input string why can it only recognize regular languages?
1
vote
0answers
37 views

Language of rationals is regular, what is the number set equivalent to PDA?

Consider rational numbers given as their decimal expansions, then for every number we can build a finite automaton able to accept it. To simplify the argument, assume that finite rational expansions ...
-1
votes
1answer
46 views

How to find what language a PDA accepts?

Given the following PDA describe the language it accepts. ...
1
vote
2answers
43 views

Complete finite automaton to never fail a match but either match original or up until the orginal

Suppose I have a finite automaton to match a simple string "abc" and I built some software around it to not only match the start of a string or a full incoming string, but rather to search through a ...
0
votes
1answer
40 views

Termination of Moore's algorithm to minimize deterministic automata

I use Moore's algorithm to minimize DFA as concluded below. We start with the complete graph with vertices Q and edges ...
1
vote
0answers
44 views

What are some applications of 2 stack pushdown automata?

What are some real world application for 2 stack pushdown automata, as i can only find pushdown automata applications in the internet
0
votes
1answer
81 views

How to draw a DFA for given language?

Give a finite state diagram for a DFA that accepts any word in the language $L = \{w \mid w \in \{a, b\}^* \text{ and }w \text{ alternates } a\text{'s and }b\text{’s and has an even number of ...
-1
votes
1answer
63 views

What input does this NFA accept?

I'm trying to find out what strings this NFA would accept. From what I understand, an empty string would work, as well as any string that has nothing but 0's. But for strings containing 1's, I'm a ...
0
votes
0answers
58 views

Describe the language generated by a given context free grammar

I had an exercise: Describe the language generated by the following given context free grammar and prove it by induction. $$\begin{align} S &\to SA \mid \epsilon \\ A &\to aS \mid bA ...
0
votes
1answer
33 views

Finding an automaton with a given number of states

Define an NFA with 4 states that is equivalant to the following Regular Expression. $(01 + 011 + 0111)^*$. My main problem is that to check for a string of length 4 (...
-2
votes
1answer
51 views

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 ...
-1
votes
1answer
53 views

Programming Thompson's algorithm: How to represent a NFA?

I'm trying to create a small program that interprets a NFA to the corresponding regex using Thompson's algorithm. My question: What kind of notation can be used to express a NFA (e.g. in the form of ...
2
votes
1answer
69 views

Deleting useless (dead) states from a finite automaton

A useless state in a finite automaton is one from which no path leads to a final state, hence no (piece of a string) is recognized out of this state. Theoretically, the algorithm to determine the ...