We changed our privacy policy. Read more.

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
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
158 views

Why don't we use $ as end marker for input in PDA?

I am reading Theory of Computation by Peter Linz. The transitions for PDA uses $\epsilon$ as end marker for input string. For example if the final state is $q_1$ then the transition is written like $\...
0
votes
0answers
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 ...
0
votes
0answers
267 views

A Turing machine recognizing languages of Turing machines

How can a Turing machine be constructed to recognize languages consisting of Turing machines that accept a certain set of strings? An example: the language $L = \{\langle M\rangle\mid M \text{ ...
0
votes
0answers
150 views

Simplification of regular expressions

$(0+1)^*.1.(0+1) + (0+1)^*.1.(0+1)$ and $(((0^*.1^*)+1)^*(0+1)^*)^*$ I have studied Arden's theorem $R=Q+RP$ has a unique solution $R=QP^*$ and some identities like $E+RR=R$ and $E.R=R$. I have ...
0
votes
0answers
89 views

Motivation behind the computational way of language translation

As I am going through learning about compilation , what I see is the approach to the subject through machines , known as automata , which change from one state to another depending on the input ...
0
votes
0answers
77 views

Doubts about a Turing Machine Problem

The following is an excerpt from the book "Introduction to the theory of Computation" by Michael Sipser, 2nd edition. As per the book, this Turing machine accepts the language L = { w#w | w ...
0
votes
0answers
234 views

How to construct this turing machine?

How can we construct TMs such that it accepts(Give description only): a + b = c a . b = c Input is of the form a#b#c. a,b and c belongs to {0,1}* and are positive binary unsigned integers. I know ...
0
votes
0answers
102 views

Providing an algorithm for a given PDA

I was asked the next question in my homework assignment: I just want to make sure that I fully understand what it is that's required of me. Am I asked to find an algorithm which decides if the ...
0
votes
0answers
174 views

Push-down Automata problem

I understand that a PDA is an automata with a stack (LIFO) but I still can't understand how to answer a very simple question like this one. I've read so many pages on it, searched all over Google, ...
0
votes
0answers
460 views

Constructing a minimal pushdown automaton for counting characters in substrings

I have to construct a pushdown automaton for the following language over alphabet {a,b,c}: L={ ucv | |u|!=|v|; u,v={a,b}* } (note: u,v are substrings over alphabet {a,b}, |u| is length of substring ...
0
votes
0answers
147 views

Does for every NFA $N$ exist NFA $M$ that has maximum 3 final states and $L(N) = L(M)$

I have a question: Does for every NFA $N$ exist NFA $M$ that has maximum 3 final states and $L(N) = L(M)$. I can answer no for DFA for below language and its minimal DFA that has 4 final states . $...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 [1] that efficacy of neural network training strongly ...
0
votes
0answers
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/...
0
votes
0answers
626 views

Describe the language generated by a given context free grammar

I had an exercise: Describe the language generated by the following given context free grammar and prove it by induction. $$\begin{align} S &\to SA \mid \epsilon \\ A &\to aS \mid bA \...
0
votes
0answers
791 views

extended transition function for NFAs

Below I am using a DFA transition function that is extended to accept words instead of just symbols. Let's say it is given that the following information is true: $$\delta(q_0, 0^3) = \delta(q_0, 0^6)...
0
votes
0answers
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)$ ...
-1
votes
1answer
48 views

I can't get the commands? each of which includes $~\$~$ instead of $~\epsilon~$ of the pushdown automaton

The pushdown automaton is given as the below diagram. What I know are as below. $$ 1,0 ~\texttt{->}~ \epsilon_{} ~~ \leftarrow~~ \text{As 1 is inputted then 0 will be popped from the stack} $$ $...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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?
-1
votes
1answer
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)?
-1
votes
2answers
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 ...
-1
votes
1answer
948 views

How to find what language a PDA accepts?

Given the following PDA describe the language it accepts. ...
-1
votes
1answer
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 ...
-2
votes
3answers
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..?
-2
votes
1answer
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 ...
-3
votes
1answer
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?
-3
votes
1answer
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?
-3
votes
1answer
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 ...
-3
votes
1answer
35 views

How can I convert a Grammar to NFA?

Hello I have a task where I´m stucking at. I have to convert a Grammar to NFA. I have these information: G=(V,T,P,S) V={S}, T{0} and S -> 0S S -> 0 I can´t ...
-3
votes
1answer
52 views

How can I convert from DFA in to regular grammar?

I have following information. 0 1 -> *q0 q0 q1 q1 q1 q2 q2 q2 q0 I have to convert this in to a regular grammar. I wrote this: ...

1 2 3
4