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
2answers
35 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
35 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
71 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
30 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
44 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
26 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
22 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
49 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
36 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
28 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
30 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 ...
-2
votes
0answers
20 views

From NFA machine diagram to a Regular Expression [duplicate]

I am attempting to give a regular expression for a NFA (non-deterministic finite automata) machine by using the step-by-step node removal technique. I introduced a new start node and a new final ...
0
votes
1answer
24 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
30 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
votes
0answers
32 views

Describe a PDA for the language [duplicate]

Let the language $$ L = \left\{ w\in\Sigma^* : w\neq xcx \text{ for any } x\in\{a,b\}^* \right\}\,. $$ Show a PDA that accepts the language. I'd be glad to get a guidance. I've heard about a ...
1
vote
1answer
25 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
71 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
31 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
93 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
66 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
128 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
54 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
56 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
38 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 ...
0
votes
2answers
50 views

Transforming NFA into DFA

In the examples I was given I have the following NFA diagram: Then it gives the conversion process Could someone explain to me the process of obtaining the second column: {1,2,4} = a{1, 2, 3, 4}, ...
0
votes
1answer
36 views

NFA not accepting a certain string

I am trying to make a non-deterministic NFA that does not contain a string "101". How do I make my NFA so that it does not have this string? My attempt:
3
votes
1answer
68 views

Product of a Transition System and a Finite Automaton

Dealing with a question that asks me to compute the product of the following transition system and finite automaton Can't seem to find a good example on how to do this so I sort of just freestyled ...
2
votes
2answers
51 views

When do we need to change the state of a push down automata? [on hold]

I'm new to the subject of automata theory. I get most of the stuff, but I cannot figure out when to change the state of the machine, and when to keep the state unchanged for a particular transition ...
1
vote
1answer
51 views

Feynman finite state machine

In his lectures on computer science, Feynman talks about finite state machines: he present a simple delay finite state machine Let me now give a specific example of an FSM that actually does ...
1
vote
0answers
29 views

Is $\{u\#v \mid u\not=v\}$ context-free? [duplicate]

Is the following language context-free? $$ \{u\#v\in\Sigma^* \mid u\not=v \text{ and } u,v\in\{0,1\}^*\} $$ You can assume $\{0,1,\#\}\subseteq\Sigma$. Unnecessary background information: I am ...
0
votes
2answers
39 views

Converting regular (Type-3) grammar to a deterministic finite state automaton

I would like to create a deterministic finite state automaton (DFA) M=(Q, Σ, δ, q0, F) that is accepting the language generated by the following regular grammar (RG) G=(N, Σ, P, S). In short I want to ...
-2
votes
2answers
53 views

I think I have a regular expression for a non-regular language

Let $W = \{a^n b^m \mid n\ge m+5,m\le 5\}$, where $\Sigma=\{a, b\}$. I have proved that this language is irregular through pumping Lemma. But through regular expression it is proving that the ...
-3
votes
1answer
35 views

Why is this sequence not acceptable for this DFA?

Why is the sequence 1100101 not acceptable for this DFA? Is it because once it reaches the final state 'q3' it can't go back to 'q1'?
0
votes
2answers
67 views

How to prove that these two languages are regular, or not regular? [duplicate]

I have these two languages $L_1={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$ $L_2={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$ As you can see that there is only one difference, the condition of ...
5
votes
3answers
153 views

How to create DFA from regular expression without using NFA?

Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that? I asked this question to our professor but he ...
1
vote
2answers
61 views

Prove correctness of DFA ending with ab

I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{a,b\}^*\}$ I know that I need to prove by induction ...
0
votes
1answer
40 views

DFA that recognizes 0 in every odd position

I had a question that asked for the DFA that accepts the following language: {w | every odd position of w is a 0 } Should this DFA accept the empty string, since ...
-3
votes
1answer
69 views

Prove A² is regular [duplicate]

Suppose that $A$ is a regular language. How can I show that $A^2 = A \cdot A$ is a regular language? Is there a construction?
-2
votes
1answer
32 views

Constructing Epsilon-closures

I am recently learning about automaton and I was confused at an exercise that was given to me. In the lecture, we were given this exercise: Given a FA with transitions $$\begin{array}{c|ccc} ...
1
vote
1answer
40 views

Which cellular automata rules are suitable for randomizing an input sequence?

S. Wolfram has in has book "A New Kind of Science" listed 256 simple rules of cellular automata. Which of these rules could via iteration essentially contribute to render an input sequence more random ...
2
votes
3answers
234 views

Why do all non-empty ω-regular languages have periodic members?

I was learning about Büchi Automata and couldn't understand a part where they were describing "Non-empty $\omega$-regular languages contain periodic strings" Let $A$ be a Büchi automaton ...
5
votes
2answers
709 views

Can a Language be determined by its kleene closure?

Lets assume that we have access to a oracle (machine that determines without details) for $L^*$, can we calculate $L$ from this machine? The cost of operation is measured by number of queries from ...
0
votes
1answer
41 views

Prove that Language is not Regular using closure(s)

I'm having a really tough time trying to comprehend proofs via closure and pumping lemma. None of the examples I can find are similar to the one's im looking to prove. Can anyone explain if I'm ...
1
vote
0answers
24 views

Number of states of finite automata [duplicate]

Prove that for each $n>0$, a language $L_n$ exists where $L_n$ is recognizable by an NFA that has $n$ states, and If $L_n=K_1 \cup \dots \cup K_k$, for regular languages $K_i$, then at least ...
0
votes
2answers
42 views
2
votes
0answers
108 views

DFA for a regular language

I have a regular language consisting of such {0,1}^k sequences, in which every subsequence of length 5 has at least two 0's in ...
1
vote
1answer
43 views

Construction of a counter automaton for the complement of the palindromes

How would I go about constructing a nondeterministic 1-counter automaton for the language $L$ that is the complement of the palindromes $\overline{L}=\{ww^{rev}\}$ over a 2 symbol alphabet $\Sigma = ...
-3
votes
1answer
43 views

A finite automaton accept no string

How can a finite automaton over(0,1) doesn't accept any string? I only can think of s->a->q->F Where the final state F is empty set. Is that true ...
0
votes
1answer
50 views

designing a DFA and the reverse of it

There is a theorem that says if a language is regular, it's reverse is regular as well. How can I draw a DFA that shows if a language is regular, it's regular as well?
0
votes
0answers
33 views

Designing a turing machine to determine if there is path from two vertices in a directed graph or not

I'm self studying automata and I'm in chapter 7 of Sipser book. I want to design a diagram for a Turing machine that shows if there is path from s to t in a directed graph. My tape is like this: ...