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

1
vote
0answers
42 views

Converting this DFA to RE using the Brzozowski Algebraic Method

Hello people, I'm trying to convert this DFA to RE using the Brzozowski Algebraic Method. (DFA created with JFlap) My Attempt Write down equations R1 = bR1 + aR2 + ɛ R2 = bR2 + aR3 ...
2
votes
1answer
106 views

Difference between regular expression and grammar in automata

I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to ...
0
votes
0answers
32 views

NFA that accepts binary strings starting with 1 and with at least 01, or at least 010, or both

Im not sure if I am understanding this question correctly. Its a problem without a solution in my text. Starting with 1, and at least 01 or at least 010 or both these substrings..... So a regular ...
-2
votes
0answers
16 views

Practical Applications of theory of computation [closed]

Apart from compiler design, what are the various fields in which theory of computation is used. As this subject is often called mother of Computer Science
-2
votes
1answer
18 views

Epsilon moves in finite automata [closed]

Is it always necessary to move from a state that accepts all valid input symbols to a next state made as final state over epsilon transitions? Why can't the state that accepts a valid string not be ...
0
votes
1answer
44 views

Executing an NFA

I am trying to verify that the NFA below does not accept babba. However, when I tried to do it by hand I must have made a mistake: $$\{q_1\}, \{q_2,q_3\}, \{q_1, ...
1
vote
1answer
22 views

What's a side-effect free expression in Timed Automata?

I'm trying to get myself more familiar with Timed Automata theory. At some point I came across the expression "side-effect free" like in the following: A guard is a side-effect free expression ...
-3
votes
0answers
25 views

question of automata [duplicate]

Both Linear Bound Automata (LBA) and Turing machine (TM) can be used to express the language accepted by above Finite Automaton (FA). Which of LBA or TM would you choose to express the given ...
-4
votes
1answer
304 views

Which of LBA or TM would you choose to express the given language and why? [closed]

Both Linear Bound Automata (LBA) and Turing machine (TM) can be used to express the language accepted by below Finite Automaton (FA). Which of LBA or TM would you choose to express the given language ...
1
vote
1answer
37 views

Converting final state PDA to empty stack PDA

I'm having a problem understanding this conversion. Let's say we have a CFL like this: $ { a^nb^m : n > m } $ A final state acceptance PDA for this language would push $A$ symbols in the stack for ...
4
votes
5answers
571 views

Is there any example of automatas (or similar) systems that emerge complex internal structures on its own?

Automatas are turing-complete grid-based systems with progression rules on which we can encode arbitrarily complex structures. For example, this is a "glider gun" on Conway's Game of Life: Due to ...
1
vote
1answer
36 views

Chomsky hierarchy type determined by language

I have some modified automata and the task is to give the type of Chomsky hierarchy to it. All task is between type 3 and 0 noninclusive. For regular languages there are lot of tools and I can check ...
2
votes
2answers
57 views

Need help constructing a Deterministic Finite Automata with AT MOST

I am stuck with constructing an DFA that has at most in it. The question I am stuck with is: Design an DFA that accepts all strings over {0, 1} that contain at most two 00’s and at most three ...
0
votes
1answer
65 views

Model paths by regular languages [closed]

I want use DFA to describe a sequence of movements in a 2D-space (language will be the path accepted by automaton in a particular case). That is a typical modeling problem: how can I encode a ...
11
votes
5answers
329 views

Defining the halting problem for non-deterministic automata

The primary definition of Turing machine (TM), at least in my own reference textbook (Hopcroft+Ullman 1979) is deterministic. Hence my own understanding of the halting problem is primarily for ...
4
votes
1answer
38 views

pda: transformation between acceptance by empty stack and final states

I am stuck with understanding the transformation of final-state acceptance automaton into empty-stack acceptance automaton. From everywhere that I've read, it always says introduce a new start state ...
1
vote
1answer
68 views

Converting Regular expression to DFA by building syntax tree

There is a way to convert regular expression to DFA (deterministic finite automata) which is to build a syntax tree and then compute first pos, last pos, follow pos, and then use a Transition ...
0
votes
2answers
32 views

Push down automata what to do when there is no suitable transition

This is a question that has emerged from a recent quiz I have taken. In short Consider the following transitions on a push down automaton. Assume the starting state is q. Which one of the ...
3
votes
1answer
367 views

The control in the Turing Machine

My question is about the control in the Turing Machine. As far as I know, the control of the Turing Machine is just a set of states. If the Machine needs to record something, it needs to write on the ...
0
votes
0answers
10 views

Construction of NPDA with inequality check [duplicate]

I'm currently struggling to construct a nondeterministic PDA with an amount of states in $O(n)$ that accepts the following language: $L = \{wcx \, | \, w,x \in \{a,b\}^n \land w \not= x\}$ with c ...
7
votes
3answers
107 views

Algorithms for minimizing Moore automata

Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times ...
2
votes
0answers
55 views

KMP Algorithm, Pratt's Minimisation/optimization of Knuth's original DFA based algorithm

The Original Knuth's Algorithm is based on DFA and it depends on the alphabet size. And Then, Pratt optimised it to be independent of Alphabet Size. But, All the ...
0
votes
2answers
63 views

How does this Turing machine accept $a^n b^n$?

I'm reading this tutorial from the University of Illinois about Turing Machines, and I don't understand something. They give a pseudocode algorithm for an machine that accepts strings from the ...
3
votes
1answer
27 views

Proof that CFL aren't closed under intersection using synchronous parallel (N)PDA composition

It is well known that the class of CFLs is not closed under intersection as follows e.g. from the following example: $$L_1 \cap L_2 = \left\{ a^mb^mc^n \mid m,n \ge 1 \right\} \cap \left\{ a^mb^nc^n ...
0
votes
3answers
53 views

Construct Turing Machine which accepts the language $ww$

I try to construct a TM that accepts the language $\{ ww \mid w \in \{a,b\}^* \}$. Between the words $w$ is no delimeter, so I don't know, how my TM can know where the first $w$ ends and the second ...
2
votes
1answer
85 views

Is this method of proving non-regularity is equivalent to pumping lemma?

I find it really difficult to prove non-regularity of a language using pumping lemma. I do understand that regular language is the language that can be expressed ...
1
vote
1answer
38 views

Can Reduction for Undecidability/Decidability Problems Go Both Ways?

This Problem sparked my question: Does a TM $M$ enter state $q$ on input $w$? I proved it was undecidable in this format using the Halting Problem as a subroutine: ...
1
vote
3answers
104 views

Is there a name for an inverted state machine?

I recently needed something like a state machine, but with a slightly different use case. In general, I would say a state machine knows about a set of states, and different events. Depending on the ...
0
votes
2answers
38 views

Transitions triggered by sets of events

In automata theory books, I always studied examples where a state transition from A to B occurs due to a single event $e$ (say, receiving a particular character). Is it theoretically possible that a ...
0
votes
0answers
36 views

Context-free with single terminal symbol — regular language [duplicate]

I have the following problem to solve: Show that if G is a context-free grammar and Σ consists of just one terminal symbol, then L(G) is regular. It is problem 4.26 from the book "Formal models of ...
0
votes
2answers
149 views

Draw a DFA that accepts ((aa*)*b)*

A homework question asks me to a draw a DFA for the regular expression $((aa^*)^*b)^*$ I'm having trouble with this because I'm not sure how to express the idea of $a$ followed by $0$ or many $a$'s ...
0
votes
0answers
40 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, ...
2
votes
2answers
52 views

DFA which visit a specific state at least once

Given a DFA M that satisfies language A, how do I modify M such that a new language B consisting of all strings that are accepted by M and cause M to enter a specific state r at least once are ...
1
vote
0answers
29 views

Example of Zeno timed automaton

Is there an example of a timed automaton that requires infinite clock precision, in order to be controller so as to avoid a deadlock or bad state? I.e. a transition system that consists of nodes ...
1
vote
0answers
28 views

NPDA, guessing capability and stack as an exclusive resource

Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA). We can view a nondeterministic transition as a guess; for example if $L = \{x x^R ...
-1
votes
1answer
54 views

DFA for regular language [closed]

I need to construct a DFA which accepts the following language: $$ L = \{w \in \{a,b\}^{\ast}\mid \#_{a}(w) \bmod 3 = \#_{b}(w) \bmod 2\} $$ I have no clue how to solve this issue. Can you please help ...
0
votes
1answer
75 views

What is the minimal number of states for the DFA?

Let the regular expression $R = ((a^*\cup \emptyset \cup \varepsilon^*)^*b)^*$ above $\Sigma = \{a,b,c,d\}$. What is the minimal number of states for a DFA accepting this regex? $1$ $2$ $4$ $5$ ...
-1
votes
1answer
48 views

Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$

Is this a CFL? $$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$ When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...
2
votes
2answers
32 views

How is regular expression law: $\emptyset L = L\emptyset = \emptyset$ correct?

I am taking a course on Automaton where I faced the algebraic laws of regular expressions. First two were ok: $\emptyset + L = L + \emptyset = L$: Union of a language $L$ with empty language ...
0
votes
1answer
75 views

Handling dead state in NFA to DFA conversion

I want to convert below NFA into DFA: I prepared below tables and finally the NFA: NFA However I feel I am wrong here, since original NFA does not have any transitions defined for state C ...
1
vote
1answer
48 views

Converting a NFA to its equivalent regular expression

I'm new to regular expressions and I'm currently working on some exercises on converting DFA's and NFA's into their equivalent regular expressions. I have the following NFA: I'm using the state ...
1
vote
1answer
33 views

How to create this pushdown transducer? (formal languages and automata)

Create a pushdown transducer that translates $a^m b^{2m}c^{m+n}$ into $b^{n-m}$, with $n\geq m \geq 0$. How should I use the stack to remember or to compute how many characters of c to read? And how ...
-2
votes
1answer
153 views

Convert RE to DFA [duplicate]

I've been trying to convert a regular expression to a non-deterministic finite automata (NFA) first using Thompson's construction, giving: , which looks correct. I am then using subset ...
0
votes
1answer
49 views

this automata is NFA or DFA?

That's my question, since it has two symbols but go to a single state, is DFA or NFA?
7
votes
2answers
122 views

Minimize Deterministic Finite Automata with no accepting states

I have a finite automaton with no final/accepting states, so F is empty. How do I minimize it? I got this on a test and I didn't know how to approach the problem because the automaton had no ...
1
vote
1answer
78 views

How exactly does a two stack pushdown automaton work?

I have to explain how a 2-PDA works and then write a program (in Delphi) which simulates a 2-PDA step by step for the language $L = \{w\$w\ |\ w ∈ \{0,1\}^n\ with\ n>0\}$. So far, so good. Now I ...
-1
votes
2answers
664 views

Regular Expression for even-odd language of string

I am new to Automata theory and would to make a regular expression for "even-odd" strings, defined over $\Sigma = \{a,b\}$, which is the set of strings with even numbers of $b$'s and odd number of ...
1
vote
0answers
65 views

How to understand and remember proofs in automata theory? [closed]

Automata theory has a lot of proofs. Sometimes I don't get how this is a proof. Take for example the equivalence of NFAs and DFAs: the proof for this statement (two-way hypothesis and conclusion) ...
2
votes
0answers
61 views

How does a minimal DFA ensure minimal computational cost?

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence: The minimal DFA ensures minimal computational cost for tasks such as pattern matching. ...
1
vote
1answer
42 views

Prove that this language is not context-free [duplicate]

I'm not very comfortable with pumping lemma for context-free grammar. I understand the sufficient conditions that must hold but proving it gets me everytime. For example, I need to prove whether ...