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

-2
votes
0answers
12 views

Constructing pushdown automata

How do you construct a pushdown automata for this particular language.
0
votes
1answer
28 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
votes
0answers
14 views

Where is my mistake in this DFA minimization?

I'm currently having trouble minimizing my DFA. I have the following graph: (ignore the numbers after ":") Using the table minimization method I reached: (x is distinguishable, O is ...
-1
votes
0answers
18 views

Question regarding minimizing of DFA

I know that the rules for minimizing a DFA is: pair of {s,t} if one is start and other is end (and vice versa), mark in table If a transition leads to pair of states which are already marked ...
1
vote
0answers
50 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) ...
1
vote
0answers
29 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
33 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
49 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
30 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
55 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 ...
0
votes
0answers
23 views

When do we need to change the state of a push down automata?

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
47 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
23 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
28 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
44 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
33 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
59 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
121 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
54 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
36 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
62 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
26 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
35 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
226 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 ...
4
votes
2answers
684 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
37 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
23 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
89 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
39 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
37 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
47 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
32 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: ...
1
vote
1answer
43 views

Is a k counter automata a special kind of PDA?

I understand that a 1 counter automata is a special kind of PDA where the stack alphabet consists of one symbol (ignoring the fixed bottom symbol) but what about 2 counter automata? Is it a special ...
4
votes
2answers
60 views

Is the number of inequivalent elementary cellular automata rules really 88?

Everywhere from Wolfram's "New Kind of Science" (p. 57) to Wikipedia they say that, out of all possible 256 (=2^8) elementary cellular automata rules, 88 are inequivalent (as defined in the Wikipedia ...
2
votes
1answer
33 views

Omega-Language to Büchi automaton

I'm currently preparing a presentation about LTL and a book says that the language $L = (a(a \cup b))^\omega$ cannot be described by any LTL (or FO) formula which is understandable but how does the ...
0
votes
1answer
38 views

Language described by inverting accepting states of NFA

Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean ...
-2
votes
1answer
40 views

Construction of an NFA knowing only the equivalence classes and some examples of L [closed]

For a certain language $L \subseteq \{a, b\}^∗$, IL has exactly four equivalence classes. They are $[\lambda]$, $[a]$, $[ab]$, and $[b]$. It is also true that the three strings $a$, $aa$, and ...
3
votes
2answers
83 views

When states that are not accepting states become accepting states in NFA, what happens?

It is known that when NFA's accepting states are swapped with rejecting states, the recognized language is not complement of the original language. For some language, it may be the case that some ...
0
votes
1answer
50 views

Making a finite automata

How can I make a finite automaton which does not end in string ab. With the alphabet a,b I made 3 states. For the first one it is accepting states and thus accept the empty string. So here is a ...
1
vote
2answers
27 views

Prove that a language is not regular with process of elimination [duplicate]

When deterministic automaton, I need to prove that you can't implement the language in it, because the language is not regular. Easiest way to prove that a language is regular, is just by making an ...
0
votes
3answers
109 views

Minimal DFA that accepts binary strings whose decimal equivalent is divisible by 32

I thought the answer would be 32 for remainder $0,1,2,\dots, 31$. But answer given as $6$. and explanation is given as if the number is $2^n$ then number of states required would be $n+1$.
2
votes
0answers
26 views

When is the best time to include an ε-transitions in a NFA state diagram?

While doing my NFA homework in my automata class, I feel like I'm not taking advantage of the ε-transitions I'm learning about. I can solve problems without using it. It's not like I really need it, ...
-1
votes
1answer
84 views

Union of two finite automata?

How do you union of two finite automata as well as establish the transition table for it. I'm unsure of how to properly union the two finite automata. I believe the transition table would look ...
4
votes
2answers
195 views

Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$. Obviously, this class is a ...
0
votes
1answer
30 views

Turing machines with a finite number of states

In a class on Turing machines, the lecturer said that the language for a machine with 100 states is both recognizable and decidable. How can we infer this just from the number of states in the ...
0
votes
2answers
96 views

How does an NFA use epsilon transitions?

In the picture I've provided, I'm trying to figure out what exactly this NFA is accepting. What's confusing me is the epsilon jump at q0. If a 0 is entered, does the system move to both q0 AND ...
4
votes
5answers
141 views

is it possible to minimize pushdown automata?

is it possible to minimize pushdown automata? If no, why? Is it because for minimization the equivalence classes need to have a finite index and we cannot guarantee that for CFG?
1
vote
2answers
32 views

Is this language regular [duplicate]

Let L is a regular language then is L' = {x$_2$x$_1$| x$_1$x$_2$ ∈ L} regular? Thus x$_1$x$_2$ is essentially concatenation of two strings, but can reverse concatenation of same two strings yield ...
0
votes
1answer
89 views

Getting minimum DFA for regular expression (11)*+(111)*

(sorry beforehand I know putting scanned diagrams may seem not-so-professional but this problem is sticking for long and its interesting too) The language corresponding to given regex seems to ...