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

2
votes
1answer
28 views

Prove that language of possible stack content is regular

So, here's the problem: Suppose that $A=(Q,\Sigma,\Gamma,\delta,s,\bot, F)$ is a PDA, let $$L = \{ \gamma \in \Gamma^* \hspace{5pt}|\hspace{5pt} \exists_{x,y\in \Sigma^*} \exists_{q\in Q}: ...
-4
votes
1answer
64 views

Order classic notions of computability by power

I need some help with a question. I'm currently studying for an exam and I could therefore use some help with this following question: Order the following formalisms (but one) according to their ...
0
votes
0answers
28 views

Adjacency matrix and transitive Closure for delete epsilon transition NFA [on hold]

I would to delete the epsilon transition from my NFA. I need to understand the transitive closure for automata; I want to create the adjacency matrix by it and at the present, I don't know if the ...
1
vote
2answers
28 views

What is the expressive power of finite-state transducers and pushdown transducers?

One would assume that a finite state transducer can perform any translation such that the resulting string is from a regular grammar. Similarly, that a pushdown transducer can generate strings from ...
-3
votes
0answers
29 views

Theory of automata [duplicate]

You are required to construct an FA and regular experssion for the language of all those strings whose length is Odd, but contain even number of b’s defined over alphabet set {a,b}.
3
votes
0answers
44 views

Context free grammar as minimal solution of a system of equations

It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example: $$\begin{align*} X &=\{{\epsilon}\} \cup Y\\ X ...
3
votes
1answer
41 views

Understanding DPA

DPA denotes “Deterministic Pushdown Automata”. Is the following (*) true regarding DPA: After all symbols of the input sequence are consumed, the input sequence is accepted either (1) if the ...
7
votes
2answers
93 views

Running programs backwards

I never used a debugger that can run a program backwards but I would like to. Now I wonder if there is much evidence and theory about backwards runnable programming, when and why a program can be run ...
-4
votes
0answers
24 views

Give the recursive inference for this grammar [duplicate]

Give the recursive inference for this grammar $S \to aSd\mid T$ $T \to bTd\mid U$ $U \to Ud\mid cU \mid c$
-3
votes
0answers
20 views

Create Turing Machine using transition table

So we started learning about Turing Machines and I do not quite fully understand it. My teacher wants us to create a Turing Machine by writing out the whole transition table, that counts in binary. We ...
1
vote
2answers
69 views

Write a regular expression - Contains an equal number of 01 and 10 subtrings

I have this language: And ive worked on a DFA where i can move on to create the RE. Here is my DFA: What im trying to do now is using ardens theorem to get the Regular expression however I'm ...
-3
votes
0answers
12 views
-4
votes
0answers
11 views
0
votes
1answer
44 views

Showing a language is context free. Use PDA or CFG?

I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it. Show language $L$ is context free, where $L = ...
-3
votes
0answers
29 views

How do I produce a regex from an automaton?

I'm confused as to whether it is required that I hit the final state or not. So far, I have (011)*(0011)*00 I don't know how to account for the path 0101011 because after that sequence, then there ...
2
votes
2answers
36 views

The importance of membership problem

Imagine a word like $w$ and a language like $L$ are given and we want to check if $w\in L$. This is called membership problem. Now i want to know the importance of this problem. Thanks in advance.
1
vote
1answer
29 views

What name for an algorithm is more correct: Kleene's algorithm or McNaughton-Yamada algorithm?

The perhaps most widely known algorithm converting finite automata into rational expressions is usually known as Kleene's algorithm. However, Sakarovitch in his book Elements of Automata Theory ...
-2
votes
1answer
35 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, ...
-2
votes
1answer
375 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\}$ ...
6
votes
2answers
103 views

How similar are two DFAs? -not just binary equivalence-

Are there any measures to compute similarity (or distance) between two DFAs? If yes, which are the main references? I need a measure of similarity, not only a (binary) equivalence test. ...
0
votes
0answers
38 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
50 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
25 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
35 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
53 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
28 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
89 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
77 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
91 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
1answer
29 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
36 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
49 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. ...
-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
30 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
48 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
37 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
41 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
52 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
42 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
68 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
39 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
36 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
78 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
39 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
195 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 ...