Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
12
votes
1answer
324 views
Eilenberg's rational hierarchy of nonrational automata & languages
In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised a Volume C dealing with "a hierarchy (called the rational ...
8
votes
2answers
216 views
Why is it undecidable whether two finite-state transducers are equivalent?
According to the Wikipedia page on finite-state transducers, it is undecidable whether two finite-state transducers are equivalent. I find this result striking, since it is decidable whether two ...
7
votes
1answer
157 views
Does there exist a universal pushdown automaton?
Let $\Sigma$ be a fixed alphabet and let $PDA(\Sigma)$ be the set of all Push-Down-Automata (PDA's) having input alphabet $\Sigma$. Is there an alphabet $S$ and a function $f:PDA(\Sigma) \to S^∗$ such ...
7
votes
2answers
341 views
A magic trick with synchronizing words
See the following magic trick. http://www.speedyadverts.com/SAEntertainment/html/realmagic4.html
Spoiler Alert
Believe it or not, the lady didn't really read your mind; she is not even a real lady ...
7
votes
2answers
186 views
Density of black cells in rule 110
Is there a way to compute the limit of the ratio (number of black cells)/(number of white cells), in the rule 110 or rule 30 automaton? With initial state = 1 black cell.
Simulation of first 120000 ...
6
votes
3answers
1k views
Why does this FSM accept binary numbers divisible by three?
This final state machine accepts binary numbers that are divisible by three. In theory the states should equal to the value $n$ mod $3$, but how does this work for binary numbers?
What I don't get ...
6
votes
1answer
83 views
Existence of NFA for this language
I'm given a task to find (and prove) such language $L$ in the alphabet $\Sigma = \{a,b\}$ with all words less than $1000$ in length, for which any DFA/NFA will have more than $10^{10}$ of states. For ...
6
votes
1answer
235 views
Automata theory on infinite words: any video lectures?
I am fun of automata theory. Can you suggest good video lectures on the subject?
(there is a good one here, but it is accessible from RWTH University only)
5
votes
1answer
63 views
Is there any relationship between the bounding box and the period of an oscillator in the Conway's Game of Life?
Is there any relationship between the bounding box and the period of an oscillator in the Conway's Game of Life?
In particular I am interested in this case: what is the maximum period for an ...
5
votes
0answers
174 views
What is the class of languages accepted by DFAs whose transition monoids are transitive permutation groups?
In the Wiki page
A permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes the set of states. ..... A formal language is p-regular ...
5
votes
0answers
313 views
Connecting finite automata and regular languages in teaching/applications
I am considering giving a presentation to middle schoolers, aged about ten to fourteen, about finite automata and regular languages.
Average American students have no problem with uses of the ...
4
votes
2answers
118 views
Push down automata problem
Informally describe the Nondeterministic PDA that generates:
$$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$
My initial plan was to use nondeterminism to go through each character before ...
4
votes
3answers
128 views
Deciding equivalence of regular languages
Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:
build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
4
votes
1answer
94 views
Is $(p,\epsilon,p)$ a path of an automaton?
$A$ is an alphabet. An automaton over $A$ can be defined
as a set $A_0 = (Q, E, I, T),$ where $Q$ is the set
of states, $E \subseteq Q \times A \times Q$ is the
set of edges or transition, $I, T ...
4
votes
1answer
52 views
Gliders, static structures in various (dynamic) systems
Structures, i.e. symmetries over time, appear in various systems:
gliders in cellular automata, like Game of Life or Rule 110,
unmatched string's parts in rewrite systems – unchanged in multiple ...
4
votes
1answer
295 views
Drawing a PDA for a language
I am initiating myself into TOC and using sort of random resources from the web.
I was looking at this problem from a Berkeley problem set:
Construct a PDA to accept
$$
L = {a^ib^j|i \neq j , 2i ...
4
votes
1answer
119 views
Minimal DFA satisfying a finite view of a language.
Say one has a language $L \subseteq \Sigma^*$, but one doesn't know what strings are actually part of the language. All one has is a finite view of the language: a finite set of strings $A \subseteq ...
3
votes
3answers
458 views
Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?
Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular?
I believe the answer is NO, but it is hard to make a formal demonstration of it, ...
3
votes
3answers
1k views
How to prove two regular expressions are identical in mathematical way?
I'm currently working on "regular expression" exercises in the textbook ("An Introduction to Formal Languages and Automata"), and the problem that I'm facing is, most of the time, my solution is ...
3
votes
2answers
59 views
Does $L=\{(\langle M \rangle,k)| M$ is a TM and $\exists w\in \sum^*$ s.t when $M$ runs on $w$, $M$ visits some state at least $k$ times$\} \in R$?
I'd like your help with understanding , how come the following language is decidable (in $R$):
$L=\{(\langle M \rangle,k)| M$ is a TM and $\exists w\in \sum^*$ such that when $M$ runs on $w$, $M$ ...
3
votes
2answers
95 views
Showing $L=\{uw \mid \exists v:uv\in L_{1},vw\in L_{2}\}$ is regular
Let $L_{1,}L_{2}$ be regular languages and define $L:=\{uw \mid \exists v\in\Sigma^{*}:uv\in L_{1},vw\in L_{2}\}$.
I wish to prove that $L$ is regular using only closure properties
(such as ...
3
votes
1answer
1k views
How to show that $ALL_{DFA}$ is in P
How can I show that $ALL_{DFA}$ is in P ?
$ALL_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^* \}$
3
votes
2answers
41 views
If $L\in REG$ then $M$ has a finite number of distinct rows
Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$:
$$
m_{x,y}=\begin{cases}
1 & x y\in L\\
0 ...
3
votes
2answers
178 views
Question about regular languages and finite automata
We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
3
votes
2answers
412 views
How to compute the transition function in non-determinism finite accepter NFA?
I'm currently teaching myself Automaton using Peter Linz book - An Introduction to Formal Languages and Automata 4th edition. While reading chapter 2 about NFA, I was stuck this example (page 51):
...
3
votes
1answer
113 views
Context Free Language? Proving through grammar?
I need help solving this question:
Is $L = \{ w \in \{a,b,c\}^* \mid n_a(w) = n_b(w) = 2n_c(w)\}$ a context-free language?
That is the number of $a$'s equal the number of $b$'s equal twice the ...
3
votes
2answers
275 views
Help in constructing a DFA equivalent to this NFA
First post here, woot. I've been a member of Stack Overflow for a while, so hopefully you guys are just as friendly!
I'm having issues converting simple NFAs to DFAs... I just don't get it. ...
3
votes
1answer
344 views
Question regarding stack operation notation in PDA
I'm currently reading two books:
An Introduction to Formal Languages and Automata, 4th Edition by Peter Linz.
Introduction to the Theory of Computation, 2nd Edition by Michael Sipser.
What ...
3
votes
2answers
132 views
Automata: 1=2, 2= 26, 3=1054, 4=5768, 5 =139314069504, 6 = ???
I am in my own Automaton (finite-state deterministic automata) research, so i have four sets of automata.
2 states automata,
3 states,
4 states and
5 states.
Input alphabet $\{0,1\}$
so...
the ...
3
votes
1answer
141 views
Proving Turing Completeness by Simulating Rule 110
Something I've heard often is that Rule 110 is the `simplest' Turing-complete formalism. As a programming exercise in a language I am new to, I implemented a function that computes from an initial ...
3
votes
1answer
435 views
If L is regular, so is $L-\{λ\}$?
A language is regular, by definition, if you can create a DFA for it. Then I need to prove that if $L$ is regular, then so is $L-\{\lambda\}$ for any $\lambda\in L$. Any ideas?
3
votes
0answers
66 views
Enhancing the monoid structure over a finite alphabet to prove Arden's rule
Suppose you have a finite-state, deterministic automaton, that you wish to convert to a regular expression. A common method, perhaps easier to apply by hand that Yamada's algorithm, is to reduce the ...
2
votes
3answers
108 views
Regular Language
Prove that the language $\{a^{k} \mid k \equiv 0 \text{ or }k\equiv 2 \pmod 5\}$ is a regular language. I am just trying to figure this problem out for my own benefit. I am new to learning this ...
2
votes
2answers
61 views
Describe a PDA that accepts all strings over $\{a, b\}$ that have as many $a$’s as $b$’s.
I'm having my exam in few days and I would like help with this
Describe a PDA that accepts all strings over $\{ a, b \}$ that have as many $a$’s as $b$’s.
2
votes
2answers
207 views
The language that contains no proper prefixes of all words of a regular language is regular
Let $L$ be a regular language. I need to prove that the language
$$M_L = \{w \in L \; | \forall x \in L \; \forall y \in \Sigma^+ : w \neq xy \}$$
that contains all words of L that do not have a ...
2
votes
3answers
195 views
What is the language of this DFA?
How would you write the language for this DFA as L(M) = {...}?
I think in English I would say L(M) is defined as {a,b}* ending in b, ba or aa.
2
votes
2answers
49 views
Giving a regular grammar for the language
I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve ...
2
votes
1answer
71 views
Is there a problem with this example?
In example $1.14$ on page $51$ (of the book and $64$ of this link), shouldn't the string $01000$ get rejected? However it seems that the first three digits of the string would force it to an accept ...
2
votes
2answers
73 views
Is this proof using the pumping lemma correct?
I have this proof and it goes like this:
We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$.
Then, the following proof is given:
There is a $p$ ...
2
votes
1answer
104 views
Would the following NFA accept all strings?
The question asks the following: "Let N be a nondeterministic finite automaton with s states. Suppose than N accepts all strings of length s or
less. Does it follow that N accepts all strings? (If so, ...
2
votes
1answer
58 views
Definition of a deterministic Pushdown automaton
According to my book the definition of a deterministic Pushdown automaton
allows for $\delta(q,\epsilon,Z)$ to be non-empty if $$\forall\sigma\in\Sigma:\,\delta(q,\sigma,Z)\neq\emptyset$$
Can someone ...
2
votes
4answers
2k views
Intersection of two deterministic finite automata?
I'm trying to solve a problem where I have to create a DFA for the intersection of two languages.
These are:
$$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every ${\tt a}$ in $s$ is ...
2
votes
2answers
106 views
How to ensure the syntactic semigroup of $X$ is the smallest semigroup recognizing $X$
Show that the syntactic semigroup of $X$ is the smallest semigroup recognizing $X$ in the sense that, for every semigroup $S$ recognizing $X$, there exists a morphism from $S$ onto the syntactic ...
2
votes
2answers
109 views
Checking if the language is a regular one
Let A = $\{x \in \{a,b\}^{*} \mid |x|_{a} = |x|_{b} \}$. Is possible to find a regular expression $\alpha$ such that $L(\alpha)$ = A ? $L(\alpha)$ is the regular language defined by $\alpha$. It ...
2
votes
2answers
1k views
Construct PDA that accepts the language $L = \{ a^nb^{n + m}c^{m}: n \geq 0, m \geq 1 \}$
Problem
Construct PDA that accepts the language $L = \{ a^nb^{n + m}c^{m}: n \geq 0, m \geq 1 \}$
My initial idea was,
If we read an $a$ push a $x$ onto stack
If we read a $b$, there are two ...
2
votes
1answer
658 views
Nondeterministic Finite Automata to Deterministic Finite Automata?
I am unfamiliar with the general process of converting NFA to DFA. I have general understanding of the theory, but I don't have the method established. Please help explain the process required to ...
2
votes
1answer
88 views
Show that this language cannot be accepted by a deterministic push-down automaton [duplicate]
How do you show that there exists no DPDA that accepts $ L = \{0^n1^n \} \cup \{ 0^n1^{2n}\}$ ?
2
votes
1answer
49 views
Constructing PDA with either one state or two states
If $L$ is a context-free language and $\epsilon \notin L $, how do you show that there exists a PDA that accepts the language by final state such that it has not more than two states and makes no ...
2
votes
2answers
1k views
Design Push Down Automata to accept palindrome by empty stack
I'm trying to make a PDA that accepts the language w001(rev w) | w = {0,1}* by empty stack,
where rev w means the reverse of w. (Stack symbol = #)
I've come up with this so far, but I don't know how ...
2
votes
2answers
51 views
Derivation of a property of a language
I am confused how this relation is derived for a language on alphabet V
A,B
The relation is
$$
(A\cup B)^*=(A^*B^*)^*
$$
I am confused how this is derived. Any pointers?
