# Questions tagged [automata]

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.

197 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
178 views

### Tool for NFA/DFA manipulation

I am look for a tool with any or all of the following features: Regular Expresstion to NFA converter that represents transitions as Binary Decision Diagrams NFA to DFA converter NFA minimization NFA ...
424 views

### Decidability of intersection of two languages of same type

Given two context-sensitive languages, $L_1$ and $L_2$ is the problem of "whether $L_1 \cap L_2$ also belongs to CSL" decidable? I have the same question for the case when $L_1$ and $L_2$ belongs to ...
332 views

### Computing substring language on automata

Given a DFA, it is possible to compute the automaton that recognizes the language of its substrings (you can compute it as the automaton that recognizes the suffixes of its prefixes). I would like to ...
35 views

### Find any kind of grammar for the language

Find any kind of grammar for the language L = {w ∈ Σ* | in w there are twice as many a's than b's} and reason its correctness. Where ...
49 views

### Is it possible to simulate oracle machines on 1-dimensional cellular automata?

My instinctual response is that it is possible, but I can't see how to simulate the oracle tape on a 1-d CA. If not, are they able to be simulated on n-dimensional CA? My thought is that the oracle ...
158 views

56 views

### How are Probability and Non Determinism Related ? Alternatives to handle Non determinism?

I have been thinking about Non-determinism in any kind of state machine. Since I work on machine learning, I tend to think that probability is a means of handling non-determinism. Instead of ...
267 views

120 views

### Reduction Theorem In TOC

If P1<=P2 means P1 is reducible to p2,then which is true? 1 If P1 is RE But Not REC,P2 is also RE but not REC? 2.If P2 is RE But Not REC,P1 is also RE but not REC? As per my knowledge,if P1 is ...
1k views

### Difference between LR parsing and Shift-Reduce parsing?

I'm learning natural language processing and I can't understand the difference between Shift-Reduce parser and LR parser. As I've understood from Wikipedia, shift-reduce is just a name of a class of ...
996 views

### Can any left recursive grammar be converted into equivalent right recursive grammar and vice versa

I know how to convert any Left Linear Grammar (LLG) to Right Linear Grammar (RLG) and vice versa. This can be done as follows: Reverse "LLG for L" to get "RLG for LR" by changing A → Ba to A → aB ...
4k views

### Removing epsilon transition from context-free grammar

I have the following context-free grammar from which I have to remove epsilon transitions: $S \to 0A0|0$ $A \to BC|2| CCC$ $B \to 1C | 3D | \epsilon$ $C \to AA3 | \epsilon$ $D \to AAB | 2$ By ...
124 views

### Find a minimal regular expression for the languge of the words that does not contain bbb

Let's say my dictionary is {a,b} I want to ccind a regular expression for the languge of the words that does not contain bbb in the most minimal way. All I can think about is '+'ing between prefixes ...
70 views

### How can I build this automaton?

The automaton has to recognize the language $(a^n)(b^m)$ so the number of $b$s is at least the number of $a$s and at most twice that number. The only thing I have achieved is to get an automaton that ...
123 views

### Reduce Nondeterminism in Pushdown Automata

I know there might be some situations where we want transitions to be only taken when the stack is empty, and transitions to be taken only when the input stream is empty. We can create an additional ...
663 views

### Converting a CFG with epsilons into a DPDA

I have a CFG: S -> $T$ T -> T+T|T-T|T/T|(T)|CX|I X -> XX |C|N|_|@ C -> a|b|c|....|z|A|B|C|...|Z|_ N -> 0|1|2|....|9 I -> NI|N Here @ means epsilon. The above is a valid arithmetic expression ...
194 views

### NFA on 3 states with equivalent DFA on at least 8 states

For all NFA $A = (Q, \Sigma, Q_0, \Delta, F)$ such that: $\Sigma = \{0,1\}$ $|Q| = 4$ There exists a complete DFA $A' = (Q', \Sigma, q_0, \delta, F')$ such that: $L(A) = L(A')$ $|Q'| \leq 15$ How ...
81 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  that efficacy of neural network training strongly ...
624 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/...
626 views

209 views

### Prove a bisimulation relation

I need to prove a bisimulation relation on $CA_{\tau}(N)$ (communication algebra with tau-steps) and names $N$. It need to prove that $p!d.x||p?d.y$ is bisimular with $p!d.(x||p?d.y)+p?d.(p!d.x||y)$ ...
48 views

99 views

### What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?

I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can ...
154 views

### Turing Machine construction of M=wwRw form

Construct a Turing machine for M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}. I tried to imagine that I will have to divide the string into 3 equal parts and check if ...
155 views

### Design a DFA recognising the following language

Design a DFA over alphabet (a,b) such that for all it's string no prefix contain two more a's than b's and two more b's than a's and the number of a's is equal to b's. Is it possible to design a DFA ...
118 views

### Constructing an NFA for a language defined over $\Sigma = \{0, 1\}$

The language is defined as $$L = \{0^n10^m10^q \mid n,m,q \in \mathbb{N}, q \equiv nm \mod 5\}.$$ Can someone help me get started on this question? I don't know what part of the question I should do ...
396 views

### Constructing PDA to accept language { 0^i 1^j 2^k | i = 2j or i = k, where i,j,k >= 1 }

$L = \{ 0^i 1^j 2^k \mid i = 2j \text{ or } i = k, \text{ where } i,j,k \geq 1 \}$ I have trouble about this PDA. Anybody can help me about draw this PDA?
17 views

### Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$

Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$ sigma is any alphabet. R is a regular expression. How can L(RR) even be a subset or equal to L(R)?
461 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 ...
948 views

### How to find what language a PDA accepts?

Given the following PDA describe the language it accepts. ...
126 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 ...
3k views

### DFA for every run of a's=2 or 3

I am trying to create a dfa for L={w: every run of a's has length either two or three} this is my attempt at the solution..i feel like I am missing something..?
1k views

### Decidability of Context free languages

Is is decidable whether 2 given PDAs accept the same language? Also, is it decidable whether the language accepted by a given grammar is context free (the given grammar could be unrestricted but ...
64 views

### Minimization of automata with dead state

I am supposed to minimize the following DFA automa, which contains dead state: But after the minimization of the automata, it stayed the same. Is it correct?
140 views

### PDA for parentheses language

Construct a PDA for the language described by the following CFG: $$S \to [S] \mid \{S\} \mid \Lambda$$ How can I develop a pushdown automaton for this language?
185 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 ...