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

Transforming an NFA to a DFA: I don't know how to proceed with multiple symbols per transition?

EDIT: Modified body of content, was unclear. I'm currently attending a course in Automata theory. I have been trying to complete an example question to better understand NFA to DFA transformation. I ...
1
vote
1answer
13 views

state complexity for an nfa given a language

I've been having trouble proving the next statement: Let $L_n=\{ww, |w|=n\}$ prove that $L^c_n$ can be accepted by an NFA with at most $O(n^2)$ states. What i've been trying to do it's that the ...
-1
votes
1answer
48 views

Converting NFA to regular expression

Here is the regular expression I made for it This is my first answer, used the naive method aka don't know what am doin' method. $$ \epsilon \cup a^* \cup (a^*b) \left((a| b^*a) | \left( ...
-3
votes
0answers
24 views

Finite Automata [duplicate]

Model marbel toy with finite automata. Exercise 2.2.1(a) from Introduction to Automata Theory Languages and Computation book. The transition table looks: My question is about this table. How to ...
1
vote
1answer
50 views

Don't understand closure under string reversal

I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function, I having breaking down ...
1
vote
0answers
47 views

Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?

Consider a nondeterministic Mealy machine, $M$, defined as follows: $M = (Q, \Sigma, \Delta, \delta, \tau, q_0)$ where $Q$ is a finite set of states $\Sigma$ is an input alphabet $\Delta$ is an ...
1
vote
0answers
26 views

Describe in English the pattern in the following regular expressions [duplicate]

Describe (in English phrases) the languages associated with the following regular expression. it says to be as simple as possible ...
1
vote
1answer
23 views

Sampling from a Acyclic Deterministic Finite Automaton

Assume you have a finite language $L$ succinctly represented as a acyclic DFA $M$ (models can't be much simpler than that :) ). How can we efficiently sample a word from $L$ with uniform ...
-3
votes
1answer
95 views

Pushdown Automata Challenge

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
-1
votes
1answer
26 views

Do NFAs with ϵ-transitions accept languages that no PDA can?

Is it correct to say that there are languages that a NFA with epsilon recognizes but a PDA is not? I think that it is wrong but I cannot find a suitable explanation.
-1
votes
2answers
54 views

Strange TM Language on Definition [closed]

i prepare for Autotmata Course Final Exam. in one of lecture, our professor draw this Turing Machine, and wrote DELTA is Neutral element of TM. it'w wrote: Language of this TM is: {$W \in ...
-2
votes
0answers
61 views

Cascading Two Mealy Machines

Let a Mealy Machine $A$ be defined by its parameters $A = (Q,S,R,F,G,q_I)$ where $Q$ a finite set of states, $S$ a finite input alphabet, $R$ a finite output alphabet, $F$ a transition function, $G$ ...
1
vote
1answer
164 views

Deciding if a finite automata accepts strings of any length

Question is you're given a DFA. Give an algorithm which tells you whether strings of all lengths $n\in \mathbb{N}$ are acceptable or not. What I doing was, I have algorithm to count the number of all ...
3
votes
1answer
35 views

Converting generalized NFAs to NFAs

I came across generalized nondeterministic finite automata (GNFAs) in Sipser's Introduction to the Theory of Computation. These are automata where transitions are labelled with regular expressions, ...
-1
votes
1answer
89 views

How to construct a DFA for this?

Let $C = shuffle(A, B)$ denote the shuffle $C$ of two languages $A$ and $B$, it consists of all strings $w$ of the form $w = a_1b_1a_2b_2....a_kb_k$, for $k > 0$, with $a_1a_2 ··· a_k \in A$ and ...
-1
votes
1answer
48 views

Why is there still nondeterminism in my automaton?

I've been solving some exercises recently and it appears my answer was wrong for this particular example. The task is to convert this NFA into a DFA: My attempt is this: Now the tool I'm using ...
-2
votes
1answer
90 views

Why is the language of even-length non-palindromes context-free?

We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$ is a context-free language. Can anyone help me produce a PDA or give me any hint how I can quickly understand why ...
-3
votes
1answer
61 views

Language of a grammar

What's the language of following grammar? $G: S \to S_1B$ $S_1 \to aS_1b$ $bB \to bbbB$ $aS_1b \to aa$ $B \to \lambda$ any hint or solution?
0
votes
0answers
19 views

Converting DFA to Regular Expression “equation-method(?)” [duplicate]

I have trouble understanding my text-book on how to convert a DFA to a Regular Expression using "equation-method"(don't no what it's called). If someone could explain step by step in detail what's ...
1
vote
1answer
58 views

Non Deterministic PDA accepted language not clear

This is a PDA from the lecture slides I'm using: They say it accepts all words that contain double a's. While it makes some sense it's not full proof. What prevents the second a to be read in the ...
4
votes
1answer
109 views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
2
votes
2answers
66 views

Language to Construct Finite State Transducer

I am attempting to write a Finite State Transducer module in OCaml, because I think it's a good exercise, which is because I have been teaching myself Natural Language Processing. You typically ...
-1
votes
2answers
39 views

How deciding if 2 deterministic finite automatas decide the same language? [duplicate]

Is there any polynomial procedure to decide if 2 deterministic finite automatas decide the same language?
-2
votes
1answer
200 views

Suffix automaton algorithm to find occurrences of substrings

Here is an attached link to a problem, the Substring query problem that I am trying to solve. It requires the use of suffix automaton,but I could not understand what is a suffix automaton. Can ...
0
votes
1answer
70 views

A DFA recognizing my name

How can I know if my DFA is implemented correctly? For example, I need to build a DFA, and then minimize it which will recognize my name. Language which describe my name is: L = {pustai, marius} I ...
-1
votes
3answers
241 views

Problem understanding DFA & NFA equivalence in Theory of Computation

Before asking this question,I had gone through Equivalence of NFA and DFA - proof by construction but my question is a bit different from that. I was reading Michael Sipser's ...
0
votes
1answer
39 views

Proof that finite automata is closed under intersection

I'm looking at a proof that says that: If $M_1=(Q_1, \Sigma , q_1, A_1, \delta)$ and $M_2=(Q_2, \Sigma , q_2, A_2, \delta)$ are two finite automata(FA) then $M=M_1 \cup M_2$ is also an FA. We define ...
3
votes
3answers
62 views

generate possible inputs valid for automata

I find lots of solution where you have an Automata and a input string , you can validate whether input string is accepted by automata or not. Can we do the reverse ? I am looking for solution which ...
1
vote
0answers
54 views

(Symbolic) Equivalence of deterministic infinite word transducers with restriction

Given a deterministic infinite word transducer (also called deterministic generalized sequential machine) with the following restriction: There is exactly one initial state All states are final The ...
0
votes
2answers
125 views

Theory of computation introductory curriculum

I want to study theory of computation on my own, so I am looking for books. What set of books would you recommend for the equivalent of a one-semester course that introduces theory of computation? ...
3
votes
2answers
98 views

Correspondence between automata and formal grammars?

From Wikipedia Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string ...
-1
votes
1answer
157 views

Model marbel toy with finite automata

I'm resolving this question of Hopcroft and et al Book. Figure 1 below is a marble rolling-toy. A marble is dropped at A or B. Levers $x_1,x_2$ and $x_3$ cause the marble to fall either to the left or ...
0
votes
4answers
134 views

How is a nondeterminisitic automaton running on an input?

A nondeterministic automaton, after reading an input symbol at some state, may jump into any of a (finite?) number of states. Does the automaton uniformly randomly choose one out of the several ...
0
votes
2answers
47 views

Can a language be the one recognized by more than one automatons?

The language recognized by an automaton is defined as the set of strings that are accepted by the automaton. I wonder if it is possible that the languages recognized by two automatons are the same? ...
0
votes
1answer
93 views

What does “finite state transduction” mean?

Wikipedia says, the regular languages are closed under arbitrary finite state transductions, like quotient K / L with a regular language. I wonder what kinds of operations "finite state ...
2
votes
1answer
72 views

Describe a TM through denotation of the transition function

I'm trying to describe a TM through denotation of the transition function. Given is a TM that recognizes the language $$ L ={\{w\#w} \mid w \in {\{0,1}\}^*\} $$ over the input alphabet: $$ ...
-1
votes
1answer
39 views

writing a Context free grammar for a language [closed]

Hi I have two question about this language: L = {a^i b^j c^k | i = 2*j OR j=2*k } 1)Finding a CFG 2)If in condition part we put AND instead of OR , is this language remains CONTEXT FREE or not ?? ...
1
vote
1answer
73 views

Turing Decidable [closed]

M = (Q, Σ, Γ, δ, q1, qaccept, qreject), where Q ={q1, q2, qaccept, qreject}, Σ = {0, 1}, Γ = {0, 1, U}, and transition function δ is as follows: ...
0
votes
1answer
51 views

Convert regular expression to Automaton

I'm trying to construct a finite-state automaton from the following regular expression: $$ (a|ba)(a|ba)^*(b|ab)^* $$ I know that from $$ (a|ba) $$ the automaton should look something like this: ...
0
votes
2answers
47 views

Recognizing a language given a Automata

I'm trying to figure out which language can be recognized in this automaton According to wikipedia here "The language L ⊆ Σ* recognized by an automaton is the set of all the words that are accepted ...
7
votes
1answer
218 views

Is the reversal of a minimal DFA also minimal?

The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with ...
-2
votes
1answer
74 views

Automata Theory Questions: Rule Trees, Context-Free Grammar, Proving Ambiguity [closed]

I'm currently taking a class in Automata Theory and it's kicking my butt. I have an assignment that my teacher gave me that consists of three questions. I have no idea where to start. My teacher and I ...
4
votes
1answer
69 views

NFAs with more than one initial state

I'm trying to give a meaningful definition for NFAs with more than one initial state. I know from the formal definition in Wikipedia that it is possible to have more than one initial state, it ...
0
votes
2answers
41 views

Automata with no transition for some character

Given an automaton and an alphabet $\{a, b\} $, and the language accepted by the automaton is $ab^*$. Such an automata can be found here: My question is: this automaton cannot process the word ...
5
votes
1answer
114 views

Where/when did Stephen Kleene first define the Kleene closure/star?

I'm working on a paper and would like to review the origins of Kleene's closure. I am unable to find any article of Kleene's that has the original definition of the Kleene closure. Is there a paper ...
1
vote
1answer
65 views

Turing machine with repeated strings

How would I go about making a Turing machine to accept the following language L? $$L = \{ www \mid w = \{0,1\}^* \text{ and } w > 0\}$$ I was thinking counting the number of symbols in the input ...
1
vote
3answers
208 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
39 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
143 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 ...
5
votes
1answer
523 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 ...