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
1answer
23 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
31 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
100 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
27 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
39 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 ...
-2
votes
0answers
34 views

Need help with finite automata? [on hold]

The following is an FA over alphaber Σ = {a, b, c}. Prove that it accepts all strings that have an odd number of occurrences of the substring abc.(top one)
1
vote
1answer
29 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
25 views

Regular Grammar and Regular Language [on hold]

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
19 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
32 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 ...
-1
votes
1answer
27 views

Transition function for PDA [on hold]

Is this correct and when so, why? $$ \delta (q_1,\epsilon,x) = (q_1,X) $$ $$ \delta (q_2,X,z) = (q_2,\epsilon) $$ It might be pretty easy, but I have read that the function design is (only a ...
7
votes
3answers
355 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
31 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
33 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
49 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
20 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
54 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
37 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
43 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
732 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
30 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
60 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
40 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
70 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
97 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
53 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
46 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
17 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
36 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
862 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
97 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
55 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 ...
0
votes
2answers
55 views

What does an NFA do if there's no transition with the correct symbol?

So I am learning about DFA and NFA, and I need some clarification for it. DFA accept empty set transition for every element in the alphabet path are deterministic NFA accept the empty set ...
-1
votes
1answer
56 views

Converting DFA to regular expression [duplicate]

I have the following DFA. (Yellow stated are accepting states.) I want to eliminate states step by step to find the regular expression of it. In my steps, I think there is a bug because I do not know ...
0
votes
1answer
51 views

How to prove that $\{0^n 1^{5n} \mid n \ge 10000 \}$ is not a regular language?

I proved that $$ \{ 0^n 1^{5n} \mid n \geq 0 \}$$ is not a regular language using Pumping Lemma by following way. Solve by contradiction that $ L = \{0^n 1^{5n} \mid n \geq 0 \}$ is regular ...
1
vote
2answers
50 views

What is the purpose of ϵ-transitions in PDA?

$A = \{a^i b^j c^k\mid i = j\text{ or } j = k; i, j, k \ge 0\}$. In its push down automaton should not there be the red colored transition instead of the black colored one?
0
votes
1answer
64 views

LR(0) expressive power

So I have grouped the following formalisms into a power hierarchy (and made classes for them): Class 1 DFA NFA NFAϵ reg.exp Class 2 (DCFL expressivity?) LR(1) DPDA Class 3 CFG PDA Class 4 ...
0
votes
1answer
61 views

Intersections of some context-free languages

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
-1
votes
1answer
45 views

Equivalence of some Automata & Language & NFA

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
0
votes
1answer
58 views

Set containment of MinimumBadPrefix and BadPrefix of a Safety Property

This question is related to formal model checking theory, but I cannot find a tag for it. Let $P_{safe}$ be a safety property. $BadPref(P_{safe})$ is the set of bad prefixes for $P_{safe}$ A Safety ...
-1
votes
1answer
100 views

How to determine the set of numbers read by a DFA from one state to another?

Using the Deterministic Finite Automaton (Q, Σ, Δ, q_0, F): Alphabet: Σ is {(0 0), (0 1), (1 0), (1 1)} Definition of Δ to strings recursively: Δ*(q, ε) = q for all q ∈ Q Δ*(q, xa) = Δ(Δ*(q, x), ...
0
votes
1answer
86 views

DFA for every run of a's=2 or 3

I am trying to create a dfa for L={w: every run of a's has length either two or three} this is my attempt at the solution..i feel like I am missing something..?
3
votes
1answer
48 views

Using induction to prove transition states are the same

Suppose that you have a DFA $M=\left(S,\Sigma,s_0,\delta,{s_f}\right)$ with $s_f\neq s_0$. Suppose further that, for all $a\in\Sigma$, $\delta\left(s_0,a\right)=\delta\left(s_f,a\right)$. Show that ...
0
votes
0answers
18 views

Classification of one-dimensional CA based on the number of inputs each cell receives during an update?

Consider Wolfram's rule 30 and Wolfram's rule 62. In the case of rule 30, only two bits of information must be passed to each new cell in the CA during an update, while for Wolfram's rule 62, three ...
0
votes
1answer
54 views

Is a door lock a finite state machine?

Must the states of a finite state machine be worked off sequentially or could you understand the different shaped parts of the key as input and the position of the pins as states? If not all the input ...
1
vote
1answer
27 views

Why does a DFA either contain all or no words $a^k$ if it loops for $a$ in all states?

I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below: Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all ...
2
votes
1answer
79 views

Computational equivalences between a calculus and an automaton model

This Wikipedia table (template for "Formal languages and grammars") maps grammar to language to abstract machine for more than a dozen languages. ...
0
votes
1answer
38 views

NFA state complexity for the complement of EPAL restricted to a fixed length

I've been having trouble proving the next statement: Let $L_n=\{ww, |w|=n\}$ (the set of equal-length palindromes (EPAL) restricted to length $2n$). Prove that $L^c_n$ can be accepted by an NFA ...
0
votes
1answer
157 views

Converting NFA to regular expression [duplicate]

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( ...