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
37 views

Prove that it is undecidable whether a Deterministic LBA accepts an infinite number of inputs [on hold]

Deterministic Linear Bounded Automaton (LBA) is a single-tape TM that is not allowed to move its head past the right end of the input (but it can read and write on the portion of the tape that ...
-2
votes
0answers
21 views

How to find the shortest common element between two sets generated by a grammar? [on hold]

Suppose I define two grammars: A = N | L (L A) B = N | L (L (L B)) Where A and B are recursive definitions, so ...
-3
votes
0answers
27 views

Grammar for permutation [closed]

What is the minimal automation that can parse a string abab into following AST? How should the grammar look like?
1
vote
3answers
65 views

Are there any steps or rules to draw a DFA?

In my first lecture of "Theory of Automata", after giving some concepts of Alphabet, Language, transition function etc. and a couple of simple automata of an electric circuit with one and two ...
1
vote
1answer
36 views

Cellular Automata Using Small Boards

I'm working on making patterns for a digital lava lamp (essentially, making interesting patterns using a 4x10 grid), and I've been looking into cellular automata. I tried implementing some variations ...
1
vote
2answers
118 views

Help me resolve my doubts about infinities, exemplified by an example of non DFA acceptable language

I have always had a hard time making sense of infinities. Example: the language $L = \{ \epsilon , 01, 0011, 000111, 00001111, ... \}$ is not DFA acceptable because a machine capable of ...
0
votes
0answers
46 views

Constructing nondeterministic pushdown automata

I having trouble constructing NPDAs for these two languages: $L_1 = \{a^nb^m \mid 2n \le m \le 3n\}$ $L_2 = \{a^nb^mc^k \mid n = m \: or \: m \ne k\}$ Would these be the proper states for the first ...
4
votes
1answer
376 views

how to draw a complement of a Turing Machine?

I am now pretty confident on how I would turn something into a Turing Machine. Now my question is how do you convert TM into a complement of a Turing Machine. From what I can remember in Finite ...
-1
votes
1answer
43 views

How to read edge labels like “01, 1” on a state diagram?

Is this state machine a moore machine or a mealy machine? I am confused because the states have outputs and the transitions have output based on the input. I tried making a state table but I think ...
1
vote
2answers
81 views

The language of TMs accepting some word starting with 101

I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language $$ L = \{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has ...
5
votes
0answers
49 views

Reduction from clique to bag automata

I am trying to figure out a reduction to prove $W[1]$-hardness for this, but I am having significant trouble. Here is the problem: Bag Automaton: A non deterministic finite state automaton ...
4
votes
2answers
54 views

What is Finite Automata Bowl?

I was trying to find info about this Finite Automata type FAB (Finite Automata Bowl) and wasn't able to find a lot. It is basically the rules that apply to PDA apply to FAB except you drop the ...
3
votes
3answers
228 views

Do all states in a DFA must be connected?

Could I construct (for some wired reason) a DFA that has a state that is not connected to anything, and it would still be legal? I'm studying for a test, and I found a question that asks if an ...
8
votes
1answer
84 views

Computing the intersection of two NPDA where it is possible

Apropois to Raphael's suggestion on Intersection of two NPDAs: Let $A_1$ and $A_2$ NPDA for context-free languages $L_1$ and $L_2$, respectively. Assuming that we know that $L = L_1 \cap L_2$ is ...
5
votes
2answers
54 views

Intersection of two NPDAs

Is there a way to take the interection of two NPDAs? I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.
2
votes
1answer
69 views

Are all DFAs also NFAs?

Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?
0
votes
2answers
59 views

How many states when converting CFG to PDA

When converting a CFG to a PDA I know that you get three main states, Qstart, Qloop and Qaccept. But Qloops will need a various amount of states, and my question is how many? Is there a way to find ...
4
votes
2answers
183 views

Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
-2
votes
1answer
24 views

Why it is said that LBA is a non deterministic Turing Machine

I have read that linear bounded automaton is a Non deterministic Turing machine. Why is it so?
3
votes
2answers
68 views

What is the distribution of Garden of Eden patterns in cellular automata with increasing pattern size?

In a given cellular automaton, such as Conway's Game of Life, is there anything known about how many Garden of Eden patterns there are by pattern size? Say, pattern size is n x n, what's the ...
13
votes
8answers
667 views

Why is non-determinism useful concept?

An automaton is an abstract model of a digital computer. Digital computers are completely deterministic; their state at any time is uniquely predictable from the input and the initial state. When we ...
2
votes
1answer
36 views

Why Deterministic PDA accepts $\epsilon$ input but DFA not

I was going through a deterministic PDA that accepts $wcw^R$ (described in Ullman's textbook), in which the last transition is given as $(q_1,\epsilon, Z_0)\to(q_2,Z_0)$, where $q_2$ is the final ...
3
votes
1answer
53 views

What is the difference between RAM and TM

In case of algorithm analysis we assume a generic one processor Random Access Machine(RAM). As I know RAM is machine which is no more efficient than the Turing machine.All algorithms can be ...
3
votes
1answer
119 views

How turing machine can be used as enumerator

Currently I am studying Turing machines and I understand that a Turing machine can produce all the strings of the language accepted by that particular Turing machine. We call such a Turing machine an ...
1
vote
1answer
23 views

In reference to the Chomsky hierarchy (and automatas), Which is the linear feedback shift register Languages/automaton?

The Chomsky hierarchy is a guideline on language expressive power. The linear feedback shift register is a very interesting "element" to structure a language and there is a large theoretical ...
2
votes
1answer
32 views

Are statecharts with parallel states NFA, DFA, or none of the above?

I'm looking for formal statements and proofs that I can make when using SCXML statecharts. As such, I'm trying to categorize it properly. SCXML supports hierarchical states. I believe that any ...
2
votes
3answers
87 views

Language Recognition Devices and Language Generators

I have few CS textbooks with me which discuss languages, well actually 2 plus old course notes supplied a few years ago. I have been searching the web too any only seem to come up with vague responses ...
0
votes
0answers
18 views

Automata Theory countably and uncountably infinite [duplicate]

I'm going over some of the pre-requisite math regarding Automata theory, and finite representations. I read the following: If ∑ is a finite alphabet the set of all strings over the alphabet (∑*) is ...
1
vote
2answers
101 views

Why are pushdown automata countable? [closed]

I began a chapter in a textbook on computational theory where they begin to talk about decidable languages. The problems in this section are pretty confusing and I honestly don't know how to begin ...
2
votes
0answers
55 views

Prove Single-Tape and Non-write Turing Machine can Only Recognize Regular Language?

Here is the problem: Prove the single-tape TM that cannot write on the portion of the tape containing the input string recognize only regular language. My idea is to prove that this particular TM ...
0
votes
1answer
51 views

Why $R\circ\emptyset$ is not always equal to $\emptyset$

I was going through the text Introduction to Theory of Computation by Michael Sipser. It is written that $R\circ\emptyset$ may not equal to $R$. I thought $R\circ\emptyset=\emptyset$ always. $R$ is ...
2
votes
1answer
58 views

What is the possible number of states in the DFA of intersection of two given FA?

Consider a DFA over $a,b$ accepting all strings having number of $a$ 's divible by 6 and number of $b$ 's divisble by 8. What is the minimum number of states in the resultant DFA ? This problem ...
3
votes
3answers
120 views

Minimum number of states in DFA for the given language?

While studying automata theory a typical problem that I face is of the following type: Constructing a DFA with minimum number of states for all strings over $\{a,b\}$ which have number of $a$’s ...
0
votes
1answer
67 views

How to generate the LR(0) finite state machine for a grammar

Here is a context-free grammar with a single nonterminal symbol S and three terminal symbols +, *, and s: S -> + S S | * S S| s My purpose is to build the LR state machine for this grammar. My ...
2
votes
0answers
29 views

Does the state of a cell in cellular automata has to be from a finite set?

In most (all I have seen) work on cellular automata, the state of a cell is from a finite set. Such as a cell can take value from a binary set, or from among few colors. Can we define the state to be ...
0
votes
1answer
55 views

Decidability Problem [closed]

given a turing machine M over the input alphabet $\Sigma $ , any state q of M and a word w $\epsilon\Sigma $* , does the computation of M on w visit the state q ? Is this problem decidable ?
1
vote
1answer
56 views

Why the given NFA is not possible

I am trying to construct NFA for all languages ending in 00. I got this and this First one I could convert to DFA by subset construction and I got the correct DFA. For the second one I got the ...
2
votes
1answer
73 views

Creating a Deterministic Push Down Automata

I saw this old post on stack overflow of a PDA that accepts a language where there are exactly twice as many a's as there are b's. The image they used is below and so is the link to the post itself. ...
4
votes
2answers
113 views

More than one NFA accepting a given language

While going through certain problems. it seems that more than one NFA is possible for the given language. Is it so? For example for drawing: NFA ending with 1 where $\Sigma=\{0,1\}$ is and also ...
1
vote
0answers
24 views

Are all PDA equivalent to two-state-PDA? [closed]

We know algorithm to convert each PDA in the underlying grammar that generates the language the PDA recognize. But we have also the algorithm for creating a two state pda from a grammar. This ...
1
vote
2answers
47 views

Prove Queue Automaton is equivalent to Turing Machine

A deterministic queue automaton (DQA) is like a PDA except the stack is replaced by a queue. A queue is a tape allowing symbols to be written (push) on the left-end and read (pull) on the right-end. ...
0
votes
1answer
33 views

Non-Deterministic FSA to Deterministic FSA, Two initial states

My method of conversion is by creating a reachable set tree and each set within the tree would represent the new states. I have never dealt with FSAs that has 2 or more initial states. How do i ...
2
votes
2answers
52 views

Can a DFA have two symbols on one arrow?

I know that a DFA has to have exactly one transition for each symbol in the alphabet, but is it allowed to have two symbols on the same arrow? If, for example, I have a DFA with states $q_0$ and ...
1
vote
1answer
79 views

Can reversing the final and non-final states of a DFA produce the complement of the original language?

Is this true? If I change all final states of a given Deterministic Finite Automata to non final states and all non final states to final states then does this new automata represent the complement of ...
5
votes
1answer
77 views

How to find a Deterministic PDA for an intersection of languages

There are two languages, $\qquad L_1 = \{w\in\{a,b\}^*: N_a\leq N_b\}$ and $\qquad L_2=\{w\in\{a,b\}^*: N_b\leq 2N_a\}$ where $N_a$ means the number of occurrences of $a$ in the string $w$. Same ...
-1
votes
1answer
87 views

Why does this automation accept the empty string?

I am new to Automata Theory. I am studying the book thoroughly and understanding it well. I have got a confusion regarding NFA. Why does this automaton accept the empty string λ? What I think is ...
1
vote
2answers
56 views

2 threads accepted at the same time [closed]

Assuming we have an automaton that simultaneously accepts a string on two paths. Would this mean that the construction of the NFA might be faulty? In other words; at the end of any string over any ...
1
vote
2answers
61 views

Direct construction of NFA for the difference of regular languages

Let $A$ and $B$ be regular languages. Let $C$ be their difference, i.e $C = B \setminus A$. Given NFAs for $A$ and $B$, is it possible to directly construct an NFA for $C$ without (implicitly or ...
3
votes
1answer
72 views

NFA to DFA final states proof

When translating an NFA into an equivalent DFA, we can say that all states that contain the final states of NFA, is the final state of DFA. What should my arguments be in order to prove this? ...
3
votes
1answer
41 views

If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons?

Is there a non-regular language over unary alphabet $\{a\}$ which has a Myhill-Nerode equivalence class that is not a singleton?