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

0
votes
0answers
12 views

Which implementation algorithms in the updated Lexers and Parsers are more advanced and efficient? [closed]

I want to write a lexer and parser based on C# language in new microsoft framework .NET Core. So I have investigation about the knowledge of implementation similar libraries. Comparison of parser ...
0
votes
0answers
44 views

DFAs can be encoded as input/output for a neural network?

I would encode DFAs (Deterministic Finite State automata) as output (or input) of a neural network for a supervised learning; it is well-known [1] that efficacy of neural network training strongly ...
-3
votes
0answers
17 views

DFA minimization using Myhill-Nerode Theorem

I must've got a blockade or something, I just can't figure out step 2 here: http://www.tutorialspoint.com/automata_theory/dfa_minimization.htm I get all the other steps, I get the initial setup of ...
3
votes
1answer
29 views

Does a NFA/DFA need a failure state?

I'm learning for my exam in theoretical computer science and I'm not sure about it, because I got different sources with different answers. So I wanted to ask here: If I draw a NFA/DFA and I maybe ...
0
votes
1answer
35 views

Modify DFA/NFA that accepts Language Subset with only Palindromes (with Size Limit)?

Given a DFA (D1) with P1 states, that accepts a language L1. Modify (D1) to create another DFA (D2), such that it will accept the language L2 that is defined as: All strings in L1 that are also a ...
0
votes
1answer
40 views

I can't understand this example of PDA Automata

looking for old tests of Language Theory, I see this exercise: Give a PDA automata that recognize the language $L = \{w \in \{a,b\}^*,\ 2|w|_a=3|w|_b\}$ They propose this solution: Can anyone help ...
3
votes
1answer
28 views

A modified version of two way DFA

Following an exercise from Hopcroft-Ullman's Introduction to automata theory: Let's define $k-MDFA$ as two way deterministic finite automaton with $k$ markers, similarly to two way $DFA$ but with ...
3
votes
1answer
38 views

Context-free and context-sensitive grammars in FSM with counters

Consider an extension of finite-state machines that utilizes a finite set $C$ of counters. Let's call them counter automata. Before execution, each counter $c\in C$ is set to zero. Every transition, ...
0
votes
1answer
24 views

Simple regular expression problem [duplicate]

new to automata theory and this is quite difficult for me so I'd appreciate a hint in the right direction if possible. We want to find a regular expression for the language $L$ over $\Sigma = {a,b,c}$...
1
vote
0answers
18 views

Size of parity automata and Buchi automata from linear time mu-calculus?

Given a linear time mu-calculus formula, there are many works on transforming the formula to Buchi or Parity automaton. Using the best algorithm, what is the size of the resulting Buchi automaton and ...
3
votes
1answer
60 views

How to Trace Path in Proof that Regular Languages are Closed Under Reversal

I'm self studying automata theory and I need help with proving that regular languages are closed under reversal. I have a basic proof, but am unsure about last statement in my proof. Is this ...
2
votes
2answers
42 views

Size comparison of NFA and minimal DFA [duplicate]

Except for isomorphisms, the minimal DFA of a regular language is unique. However, is it possible that an equivalent NFA has less states than the minimal DFA? If so, what is the reasoning behind this? ...
1
vote
1answer
27 views

Turing Machine remembering copied symbols

So, I now that any multiple-tape TM can be in theory turned into one-tape TM. However, it is too easy to copy lets say binary number from one tape to another. Thats why I thought about putting a ...
-1
votes
2answers
133 views

Finding nfa or dfa for a language [duplicate]

I'm trying to study for the summer ahead of class I saw this question, please how do I go about it? Find NFA/DFA for the language $L = \{0^n1^n : n \in N\}$
-2
votes
2answers
54 views

Find a DFA for a finite set of palindromes

Since every finite language is regular, I'm trying to find how would a DFA for the following language $\{xx^R \mid x \in \{a,b\}^*, |x| = \ell\}$ look like. Would there be one DFA for all words of ...
2
votes
1answer
90 views

Union of a Deterministic Context-free language and a Regular Language is a Deterministic Context-free Language

In formal language theory, deterministic context-free languages (DCFL) are a proper subset of context-free languages. They are the context-free languages that can be accepted by a deterministic ...
1
vote
1answer
47 views

NFA to accept strings where the third AND the third-last element are b

Alphabet is {a,b}, the third element from the start must be "b" (e.g: aab..., abb...) and the third-last element must also be "b" (e.g: ...baa, ...bbb). I can do them separately but at the same time I ...
3
votes
1answer
31 views

Is a PDA's stack size linear bounded in input size?

I was thinking as follows: At each step, a PDA can put arbitrary many symbols onto the stack. But this number is constant for every individual PDA, so it can't be more than, say, $k$ symbols per step. ...
2
votes
1answer
32 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}: (s,x,\bot)...
-4
votes
1answer
72 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 ...
1
vote
2answers
41 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
56 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
44 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
118 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 ...
1
vote
2answers
78 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 ...
0
votes
1answer
46 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 = \{\text{...
4
votes
2answers
60 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. Why is the membership problem important?
1
vote
1answer
56 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
42 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
1k 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\}$ and $...
6
votes
2answers
112 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. "Similarity"...
0
votes
0answers
40 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: http://www.myoops.org/cocw/mit/NR/rdonlyres/...
-3
votes
1answer
53 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 ...
1
vote
1answer
31 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 ...
4
votes
3answers
60 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 ...
2
votes
2answers
89 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
31 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
95 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
83 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
95 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
31 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
42 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
52 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
53 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 r_0,\dots,...
0
votes
0answers
38 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
51 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
38 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
43 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 ...