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
66 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
29 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
31 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 ...
-1
votes
0answers
33 views

Can Push Down Automaton (PDA) with n-stacks be equally powerful to a Turing machine ? [duplicate]

Can Push Down Automaton (PDA) with n-stacks be equally powerful to a Turing machine while dealing Context Free Languages (CFG)?
0
votes
1answer
34 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
31 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
36 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
52 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
30 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
38 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
71 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
38 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
20 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
70 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
23 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, ...
-3
votes
0answers
26 views

Make PDA for $0^n 1^{2n}$

I have to make a PDA for the above language. I've read and studied many PDA examples but in all of them I have to deal with an equal number between two numbers, for example I can easily make a PDA for ...
-1
votes
1answer
46 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
163 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
28 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
53 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 ...
3
votes
5answers
113 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
30 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
70 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 ...
1
vote
1answer
39 views

Regular and not Regular Grammar

According the Peter Linz Book, am a confusing about the two example the Grammar G1 = ({S},{a,b},S,P1) with P1 given as S -> abS|a and G2 = ({S,S1,S2,},{a,b},S,P2) S -> S1ab S1 -> S1ab|S2 S2 -> a ...
0
votes
1answer
41 views

Regular Grammar and Regular Language [closed]

From Wikipedia, Regular Language All finite languages are regular. and Also Regular Grammar, is a way to describe the Regular Language Right regular grammar (also called right linear ...
1
vote
1answer
24 views

Is it possible to “unshift” onto a queue using this theoretical “queue automaton”?

I have been playing Manufactoria, a game in which one has to build a production line that tests/modifies "robots". Each robot has a "tape" where each cell is colored either red, green, blue or yellow. ...
0
votes
1answer
40 views

How to make a Post Machine for $a^nb^n$?

I have tried to make a post machine for that all words of the form $a^nb^n$ by the following steps. add a marker '#' read first 'a' read next 'a's and add them read first 'b' read next 'b's and add ...
7
votes
3answers
513 views

Why is the Kleene star operator also called the Kleene 'closure' operator?

I've found that if I don't understand the etymology behind a cs/programming term, it usually means that I've missed or misunderstood some important underlying concept. I don't understand why the ...
0
votes
0answers
36 views

$L = \{x\#x^R \mid x\in\{0,1\}^* \} $ not accepted by a queue automaton?

It can be proven that class of languages accepted by queue automata is equal to class of languages accepted by Turing machines. It was mentioned somewhere that the language $$L = \{x\#x^R \mid ...
0
votes
2answers
39 views

Intersection of regular and not regular

$L_1=\{a^n\mid n\ge1\}$ is regular and $L_2=\{a^{n^2}\mid n\ge1\}$ is non-regular. We know that $L_1\cap L_2$ is regular but, here $L_1\cap L_2=L_2$; and $L_2$ is not regular. How is this possible?
4
votes
0answers
65 views

context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, $$\begin{align*}S &\to AB \mid c\\ A &\to aAb \mid c\\ B &\to bBa \mid c\ . \end{align*}$$ ...
3
votes
1answer
21 views

Automata for languages derived from an automaton by number of state visits

My question in response to this answer: what would the finite automata look like for $L_1$ and $L_0$ in the answer? I get how the languages are formed; however, since $M_L$ cannot remember how many ...
2
votes
1answer
66 views

NFA - string acceptance (decision problem) test

I am interested in testing for a given string (w) whether it is in the language (L) defined by a nondeterministic finite automaton (A). I have some blurry point in my mind. What is the complexity of ...
0
votes
1answer
38 views

Given family of grammars, determine if LR(k)

Parsing family of grammars, determine if LR(k) I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him ...
1
vote
0answers
45 views

Using A* to find the word closest to an input rejected by a finite automaton

In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton ...
3
votes
4answers
755 views

What is the point of finite automata?

Why learn finite automata when Turing machines do exactly the same thing? Turing machines accepts the same languages and more so what's the point?
2
votes
0answers
31 views

For $\sum = \{ 0,1 \}$, $A$ has strings which contain a $1$ in their middle third, and a $B$ which contain two $1$'s in their middle third [duplicate]

Language $A$ can also be represented as, $$A = \{ uvw \mid u,w \in \Sigma^*\text{ and, }v \in \Sigma^* 1 \Sigma^*\text{ and, }|u| = |w| \ge |v| \}$$ Language $B$ can also be represented as, $$B = \{ ...
2
votes
1answer
70 views

Help on using the pumping lemma?

I'm trying to prove that a language is not regular. That language is: {w ∈ {a, b}* | amount of a's in w is equivalent to the amount of b's in w, mod 2}. I have an inkling that this language is not ...
-2
votes
1answer
50 views

NFA: Regular Language that starts with ab but does not end with ab?

$L = \{x \in \{a,b\}^* \mid \text{$x$ starts with $ab$ but does not end with $ab$}\}$ I'm having trouble making a table for this NFA. I tried a few sketches out of the diagram and I can post them ...
1
vote
1answer
97 views

How to write a DFA where the second digit is equal to the last digit of binary strings?

I'm having some trouble writing a DFA for the language $$\{w =b_1\dots b_k \in\{0, 1\}^* \mid b \ge 2 \text{ and } b_2=b_k\}\,.$$ What I thought for this is writing a DFA where there are 4 states, ...
2
votes
3answers
106 views

Computing the closest match of an automaton and a string

I have a problem where I'm trying to find an efficient algorithm for approximate string matching for an input to the closest string match from an automaton (the input is assumed to be not accepting ...
0
votes
1answer
56 views

PDA - Sum of Two Characters = Sum of Two Other Characters

For one problem I have to solve, I'm given a Language: L = {a^r b^s c^t d^u | r+s = t+u} And from it told to construct a PDA that accepts it. I can construct a ...
-1
votes
1answer
52 views

Simple Pushdown Automaton

I'm currently learning about PDAs and their power when constructing them from Context-Free Grammars, however I'm still unsure of how to properly construct a CFG, and then a PDA from that CFG. In the ...
2
votes
0answers
18 views

Simulate NPDAs with DTMs using only polynomial overhead

We know by polynomial-time parsing algorithms like the classical CYK algorithm that $\mathrm{CFL} \subseteq \mathrm{P}$. Furthermore, it is easy to show by direct simulation that $\mathrm{DCFL} ...
0
votes
1answer
40 views

Can a DPDA be created for a Language which includes the null string?

Can a DPDA be created for a Language which includes the null string? The way I understand it, in a DPDA, you can have at most 1 move from any instantaneous description Delta(q,a,Z) where q is a ...
6
votes
3answers
865 views

How to XOR automata?

Say we have 3 DFAs. We know how to OR, AND, or NOT them. But how does one XOR them? There is not one single mention of this online. $x\; \mathrm{XOR} \;y\; \mathrm{XOR} \;z = ((x|y)(\neg x|y)|z) ...
3
votes
1answer
108 views

Efficient simulation of an NFA, while preserving the paths to the accept states

The standard way of simulating an NFA on a computer (for implementing regex engines etc) is to construct a DFA that accepts the same language. Otherwise you get problems like exponential blowup. ...
0
votes
0answers
16 views

DFA transtion table [duplicate]

I have the following DFA transition table for the regular expression ab. I don't understand these hyphens.As we know DFA is a deterministic automata and each state is defined for both a and b. ...
-3
votes
1answer
128 views

Creating a DFA that only accepts number of a's that are multiples of 3

I am brand new to DFA's and my first exercise requires me to create a DFA instance such that the number of a's in the string is a multiple of 3. We only have two types of symbols: a, b. To my ...