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

-3
votes
1answer
31 views

NFA with epsilon transition

I need to understand the epsilon transition for NFA, for example I have an NFA with four states q0, q1, ...
-4
votes
0answers
28 views

Recursive sets in linear bounded automata [on hold]

Why are the sets accepted by linear bounded automata are recursive.Justify your statement with suitable example.
-2
votes
1answer
106 views

Difference between DPDA and NPDA?

What are the major differences between Deterministic Push Down Automata and Non-deterministic Push Down Automata? Which one is faster and how? Also what are the drawbacks of DPDA with respect to NPDA. ...
-1
votes
1answer
42 views

Are these languages are regular?

Consider the languages $L_1, L_2 \subseteq \sum^*$, where $\sum=\{a,b,c\}$. Define $$L_1/L_2 = \{x : \exists y \in L_2\ such\ that\ xy \in L_1 \}$$ Let $L_1 = \{a^nb^nc^{2n}: n \ge 0\}$ ...
1
vote
1answer
31 views

How similar are two DFAs? -not just binary equivalence- [on hold]

Are there any measures to compute similarity (or distance) between two DFAs? If yes, which are the mainly references? NB: I need a measure of similarity, and not binary equivalence test.
0
votes
0answers
37 views

How do I show that M1, M2 are two Turing machines such that L(M1) ⊆ L(M2)?

I am currently studying for a midterm tomorrow and my professor gave us links to backtests online. This is problem #3 in the following back quiz: ...
-3
votes
1answer
49 views

Prove that TM does not decide this language

So my problem is how can I show that this TM does not decides this language. $$L = \{a^nb^nc^n\ |\ n \geq 0\} $$ It might be a basic problem and seem silly to you but still I do not know how to ...
0
votes
1answer
24 views

What are the steps/tricks/tips to construct a Büchi automaton from a given language?

Let's say I have this language: $(a + bc)^∗((b + c)a^ω + (abb^∗)^ω)$ It seems pretty complicated, where should I begin with if I were to construct a Büchi automaton? I've been doing it the ...
2
votes
2answers
31 views

What is the difference between finite automata and Büchi automata?

as the title suggests, I was struggling to define the differences between finite and Büchi automata and how they are represented. From an assignment I'm working on, this automaton can be depicted ...
1
vote
2answers
42 views

Turing machine states, lost in the jungle

There is a lengthy discussion going on at the English Language & Usage StackExchange site suggesting various synonyms for dead code, and it got me wondering about an angle that wasn't covered -- ...
0
votes
1answer
24 views

Isomorphism of a DFA and the minimal DFA

I have a DFA A, I minimize A and the minimized DFA obtained is M. My question is if in general A and M are isomorphic?
0
votes
3answers
86 views

Design an NFA to accept a, ad, abc, abd, but not e, abcd?

I've made the following diagram to accept a, ad, abc, abd but I don't it to accept e, abcd, how can I limit that? Updated I modified the diagram in another attempt:
6
votes
1answer
74 views

Why do we study closure properties of formal languages?

In automata theory we study formal languages like Regular, CF, CS and etc. and each of them have their own closure properties under union, intersection, star and etc. . I like to know, why it is ...
1
vote
1answer
90 views

How do I describe a DFA?

Consider the alphabet E = ${[abc] : a, b, c \in 0,1,...,9)} $ Example [234], [567], [897] are symbols of the alphabet. For a string $w \in $ let n(w) denote the number represented by $ w $: ...
-1
votes
0answers
11 views

non-deterministic automaton [duplicate]

I am a linguistics and I start to read some books about NLP.I have need help to solve this question. Design a non-deterministic automaton and regular expression over the alphabet {a, b, c} that accept ...
-1
votes
1answer
27 views

Why do these NFAs need epsilon transitions?

In the picture below, I'm trying to figure out why there's a need of epsilon in there and what would be the difference if we didn't put epsilon.
2
votes
1answer
34 views

Difference between a minimal DFA and a canonical DFA

given a language L,a DFA M that recognize L is minimal if M is the DFA with the minimum number of states. In order for this to happen M does not have neither unreachable nor equivalent states. The ...
1
vote
1answer
50 views

Regular expression for a finite automaton appears to be wrong

For the following finite state machine: The language recognized by it is given to be: $0+(10+11)(0+1)^*$ in my samples book, which I think is clearly wrong, since there's no return path to the ...
0
votes
1answer
48 views

If L is a regular language then the language replace(L,σ,τ) is also regular

I am stuck at the following problem: Prove that if $L$ is a regular language over some alphabet $\Sigma$ and that $\sigma, \tau \in \Sigma$, Then the language $replace(L,\sigma,\tau)$ is regular. ...
-1
votes
0answers
25 views

If a CFG has a word with length more than its variables then the language of it is infinite?

Grammar G have n variables in normal Chomsky form, It can build a word with length w, using m rules. Which disprove each of following statements: If w > n then the language of the grammar G is ...
-3
votes
1answer
16 views

Equivalence of DFA' definitions

According to wikipedia DFA accepts word $w$ by one of two definitions: A word $w$ is accepted by $M$ if $\hat\delta(q_0,w)\in F$. A word $w=w_1w_2\dots w_n$ is accepted by $M$ if $\exists ...
0
votes
0answers
25 views

Example of timed automata parallel composition

Is there any example of timed automata parallel composition? How these 2 timed automata can be combined in parallel composition (with sync)? Time automaton 1: Time automaton 2: What I know about ...
1
vote
1answer
44 views

Why do we pop the dollar symbol when it's already present in the stack in PDA?

Could anyone tell the reason for popping the top of stack(dollar symbol) as said in this lecture(p.54) when there's already dollar symbol in the stack. I would like to know if we could replace the ...
0
votes
1answer
36 views

What happens when ε-clos(X) contains duplicate elements? Example: (1+0)*1

I am learning about state machines from the Stanford online cs143 course. Here I have tried to build a nondeterministic finite automaton for the regular expression ...
2
votes
2answers
34 views

Closure under reversal of regular languages: Proof using Automata

I have been studying the closure properties of regular languages, referencing the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman. Under the ...
3
votes
2answers
39 views

An NFA with no equivalent DFA with fewer than $2^n$ states: Example and Proof

I have been following the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman. I came across the following topic titled Bad Case for Subset ...
-1
votes
1answer
49 views

Can a DFA just have one state that is both the initial state and the final state?

so im trying to create a DFA for a language that has an infinite number of possible strings over the alphabet {a,b}. can i not just have one state (initial and final state) that loops a,b to itself? ...
3
votes
1answer
34 views

Unary notation representation in Turing Machine

What can be a good convention to represent positive and negative integers in unary notation on a Turing machine? I want to design a Turing machine which acts as a subtractor.So should I partition the ...
3
votes
1answer
66 views

How many languages exist over a finite alphabet?

I'm currently reviewing my Automata and Languages Theory course and I stumbled upon the following exercise exams. Link In "Exercises for ACS 1, Fall 2004, sheet 1", exercise 1 item C, the question ...
3
votes
1answer
37 views

Linear Bounded Automaton that accepts all strings

I'm currently reading Sipser's Introduction to the Theory of Computation, and I'm reading up about linear bounded automata, now we know from Rice's Theorem that whether a TM can accept all strings in ...
0
votes
1answer
34 views

Pushdown Automata: How can I recognize a ratio threshold between two symbols in a string?

I'm trying to design a pushdown automata where there are two symbols in the alphabet and the accept state is when there is >= 60% of symbol A. I'm trying to think in terms of what to save on the ...
-2
votes
1answer
69 views

Count number of automata with 3 states and alphabet of size 2

How many different finite automata are there that have 3 states $q_0$, $q_1$ and $q_3$, have an alphabet of size 2, and where $q_0$ is starting state?
0
votes
1answer
9 views

Relation of deterministic push down automata and lower elementary recursion

Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata. Deterministic context free languages can be recognized by a ...
0
votes
1answer
37 views

How is CFL-reachability solvable in exponential time and space?

I have read a paper which mentions that CFL-reachability is solvable in exponential time and space. Intuitively, I suppose that one need to explore through all the sub-paths in the PDA for a CFL. ...
1
vote
1answer
117 views

Deterministic vs. Non-Deterministic PDA?

The following is an example of language $a^nb^n$ where $n \geq 1$ From what I have heard that in finite state machines if you see epsilon moves, then it is NFA otherwise it is DFA. But in this ...
0
votes
1answer
19 views

Does preparing min DFA by combining equivalent states always result in min DFA

I know the following fact: If $Ma_N=\{w:n_a (w)=Nk,k≥0\}$, then Number of states in $$Ma_{N1}×Ma_{N2} =Ma_{N1}∪Ma_{N2} =Ma_{N1}∩Ma_{N2} =Ma_{N1}-Ma_{N2} =LCM(N1,N2)$$ where $n_a (w)$ is the ...
6
votes
3answers
239 views

Why should we study all the three forms of representation of finite automata?

DFA, NFA and epsilon NFA all the three allow us to represent a particular regular language. With any of those representations we can arrive to the same regular expression, then why do we need to study ...
7
votes
1answer
53 views

Proving that a (tree) language is not Buchi recognizable

I'm reviewing some notes about tree automata and I'm trying to conclude a proof that the professor left incomplete. The statement is: Let $A = \{a,b\}$ and $T = \{t \in T_A^{\omega} \mid ...
3
votes
2answers
34 views

How do cycles of non-consuming transitions in NFAs influence their halting properties?

I am in a class that is going over NFAs. The way they are described is a set of states, one of which is the start state, zero or more are accept states, and one or more transitions between them, which ...
-1
votes
2answers
50 views

DFA for $L_1={w:(n_a(w)+2n_b(w)) mod 3<2}$ and $L_2=\{w:(n_a(w)+2n_b(w))\text{mod 3}<2\}$

I stumbled upon this file on scribd, which gave some interesting problems on constructing DFA. So I went on solving them, until I came across one for which result DFA is not drawn but are described in ...
0
votes
1answer
33 views

Are accepting states and unaccepting states distinguishable?

Is it true that for all DFA that if $A$ is an accepting state and $B$ is not, that $B$ is always distinguishable from $A$. I don't think it's true, just because I think I can create a DFA. $B$ reads ...
5
votes
1answer
47 views

Clarification of the definition of a POMDP

From what I understand, a $MDP=(G, A, P, R)$ (markov decision process) is represented as: A complete directed graph $G=(V, E)$ A set of actions $A_u$ for each vertex $u \in V$ A reward function $R$ ...
0
votes
0answers
15 views

Proving right quotient of two languages [duplicate]

I know that if a language $L_1$ and a language $L_2$ are regular, then $L1/L2$ is regular. When we construct a DFA $M'=(Q, \Sigma, \delta, q_0, F)$, for each state $i$ we can make $i$ the start ...
2
votes
2answers
110 views

Is it legal to draw an NFA with fewer nodes than what I normally see?

Is it Ok to express an NFA accepting 1*0 like the one above? All examples in books are represented like the bottom one. I'd like to know is that only a convention or it must have two extra nodes?
1
vote
0answers
24 views

Upper bound of automaton states for SLR parsing

How do I tell, given a specific grammar, which is the upper bound for the number of states of a LR(0) or LR(1) automaton for its SLR parsing? My guess is that generating the canonical item collection ...
0
votes
2answers
100 views

How would a DFA be designed to accept a language defined as the string comprised of every other character in each string in another language? [duplicate]

For example, you have a DFA that accepts the language comprised of strings aabbbaa and aaabbbbaaa, and you want to create a new DFA that accepts a language comprised of strings abba and aabba (strings ...
-1
votes
2answers
80 views

proof using induction of automaton

How I can explain this. Consider the following automaton, $A$. Prove using the method of induction that every word/string $w\in L(A)$ contains an odd number(length) of $1$'s. Show that there are ...
0
votes
1answer
118 views

Finding a small Moore machine that checks the last four bits

I am looking for a Moore finite state machine that returns true if and only if the last 4 bits (the input is of bits) are 0011 or 0101, the FSM can return any value at the first 4 bits (yes, even at ...
7
votes
3answers
231 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
45 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 ...