# Tagged Questions

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.

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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}$...
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 ...
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 ...
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? ...
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 ...
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\}$
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 ...
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 ...
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 ...
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. ...
32 views

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 ...
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 ...
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 ...
46 views

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"...
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/...
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 ...
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 ...
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 ...
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 -- ...
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?
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:
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 ...
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$: ...
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.
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 ...
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 ...
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. ...
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,...
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 ...
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 ...