Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
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) ...
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?
0
votes
2answers
30 views
Confusion related to a property of languages on some alphabet V
I came across this relation betwen tww sets of languages formed from the alphabet V.
A,B
The relation is
$$
A^*\cup B^* =((A\cup B)^*)^*
$$
I am confused how this is derived. Any pointer?
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 ...
1
vote
1answer
152 views
Examples of epsilon transitions
I understand the meaning of epsilon transitions, but could someone give example where epsilon transition becomes handy?
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 ...
2
votes
1answer
62 views
Is $f$ is computable by a finite automaton, the dual of $f$ is thus computable also?
et $A$ be a finite alphabet. Let $A^*$ denote the language of all words in $A$, and $\epsilon$ the empty word. Let $\rho : A^* \to A^*$ denote the "reverting" map, that transforms $a_1a_2\ldots a_n$ ...
1
vote
1answer
215 views
A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$
The following is an exercise in a book I am reading:
Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words
over $\Sigma$ that do not contain $ab$ as a sub-word.
Find a regular ...
0
votes
1answer
55 views
Regular expression arithmetics
What are the rules of regular expression arithmetics ?
For example: Let $\Sigma=\{0,1\}$
$1. 1+01=(\epsilon+0)1$.
$2. (\epsilon+00)^*=(00)^*$
0
votes
1answer
97 views
A question about the regular languages being closed under Boolean operation (how to generalize)
I know that if $L_{1},L_{2}$ are regular languages then so is $L_{1}\cap L_{2},L_{1}\cup L_{2}$
are regular languages, I also know that $L$ is regular $\implies L^{c}$
is regular
.
It is easy to ...
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
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$ ...
1
vote
1answer
78 views
Random cellular automaton with three colors.
Does exist a Cellular Automata Rule that is RANDOM (like rule 30) and has 3 colors?
I mean, as Wolfram says in his book, rule 30 shows a random behavior with some limits. But this happens using 2 ...
0
votes
1answer
61 views
How to prove that the language of a DFA is some $L$
Consider the following DFA:
It is quite clear that the language of this FDA is all the words that don't have the word $aa$ as a subword.
My question is: How can I formally prove that this is the ...
0
votes
2answers
185 views
DFA and NFA equivalent language
I'm asked to build a DFA A and NFA B such that L(D) = L(N) with some specific conditions. I'm not asking for solutions or answers; I just wanted to make sure I have the right method to attack this ...
0
votes
1answer
70 views
Help with set notation?
I want to describe the set of all words in the following format: a0w1
where a represents EITHER 0 or 1, and w represents {0,1}*
So 00011 is valid as is 1010011, etc. etc.
I'm really new to set ...
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 ...
2
votes
1answer
103 views
Is the set of codes of Deterministic Finite-State Automata a regular language?
Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
2
votes
1answer
77 views
Conditions for: $xy=zw$ and $yx=wz$
Let $x,y,z,w$ be finite strings. Find the necessary and sufficient conditions for the following two equations to hold simultaneously: $$xy=zw$$ and $$yx=wz$$ Automata Theory is new to me and i am ...
0
votes
1answer
67 views
something that looks sort of symmetrical but also not
Given the set $S_0$ of finite binary strings whose digit sum is congruent to 0 mod 2 and the set $S_1$ of finite binary strings whose digit sum is congruent to 1 mod 2,
what are the implications of ...
8
votes
2answers
212 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 ...
0
votes
3answers
160 views
Different version of pumping lemma and how to prove it
I have a question to solve but I am not even getting a direction to start or how to narrow down this problem. Please provide in your inputs.
Consider the following version of pumping lemma.
For any ...
1
vote
1answer
58 views
How to formally describe this Uppaal automata?
I have the following simple automata:
What I'm looking for is a formal description of this based on the definition here
$A=(\Sigma,\Gamma,S,s_0,\delta,\omega, F)$
How to declare all the ...
2
votes
2answers
205 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 ...
1
vote
2answers
105 views
Pushdown Automaton
Can someone help me construct a pushdown automaton to recognize the following regular expression representing the language $(a^3+a^5)$* using as few states as possible? How can this be done using a ...
1
vote
1answer
118 views
Which automata recognise the algebraic numbers?
I am reading historical stuff on the algebraic and transcendental numbers. Descartes, in his Geometry, excluded all curves not expressible as algebraic equations. Later, Leibniz called such curves ...
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 ...
4
votes
1answer
51 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 ...
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 ...
2
votes
1answer
171 views
Constructing finite state automata corresponding to regular expressions. Are my solutions correct?
I have drawn my answers in paint, are they correct?
(4c) For the alphabet {0, 1} construct finite state automata corresponding to each of the following regular expressions:
(i) 0
My Answer 4ci
(ii) ...
5
votes
1answer
62 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 ...
2
votes
1answer
112 views
Two elementary question on automaton and language
1.What is the definition for a semigroup(or monoid) recognizing a set of words(or language)?2.Are recognizable,rational and regular equivalent to each other with respect to a language?
PS:The reason ...
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
108 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 ...
0
votes
0answers
181 views
Deterministic Finite Automata: State Diagram Notation
Refer to the paper Radu Grosu, "Finite Automata as Time Invariant Linear Systems - Observability, Reachability and More". I have a problem understanding the state transition diagram of DMA $M_1$ in ...
4
votes
1answer
294 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 ...
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 ...
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 ...
6
votes
1answer
234 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)
0
votes
1answer
56 views
Modelchecking on Automata, $\phi$ not SAT and $\phi \models$ False
Given a formula $\phi$
Is $\phi \models FALSE$ equivalent to $\phi$ not SAT?
Or does $\phi \models FALSE$ means that $\phi$ is never $TRUE$ and $\phi$ not SAT means, that there existst at least one ...
0
votes
1answer
157 views
Proving that a grammar generates a language
Since every context free grammar is equivalent to a Push down automaton, to show that a grammar $G$ generates a language $L$, is it sufficient to draw a PDA equivalent to $G$ and then show the PDA ...
1
vote
3answers
154 views
Showing that two regular expressions represent complementary regular languages over {0,1}
How do up you show that two that the regular expressions, such as $(01+1)^*$ and $(0+1)^*\left(0 + 00(0+1)^*\right)$ represent complementary regular languages over $\{0,1\}$? I'm trying to do some ...
1
vote
2answers
58 views
Why this lemma is true?
Let $\Sigma$ be an alphabet of size $|\Sigma|=k$. Let $w\in\Sigma^*$ be a word over $\Sigma$. If $|w| > 2^k$, then $w$ contains an infix $y$ with $|y|\ge 2$, such that every letter occurring in y ...
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 ...
1
vote
1answer
69 views
Show that $a^k w b^k$ when $|w|_a$ is divisible by $3$ is not regular
I want to show that $L = \{ a^k w b^k \mid k \geq 0, w \in \{a,b\}^*, |w|_a \text{is divisible by }
3 \}$ is not regular.
I tried to use Pumping lemma as follows:
Let $p$ be pumping length. $a^pb^p ...
0
votes
1answer
142 views
Properties of a valid DFA
Is a DFA required to have transitions on each input symbol from each state defined? If there isn't a path from state q1 to another state on input a for example, does that invalidate the DFA itself. ...
0
votes
1answer
139 views
How do I write this formally?
For every number N in a sequence of numbers it is true that each odd N is followed by 0 or more other numbers (not including 0) then the number N+1.
How do I write this formally?
This is my attempt ...
3
votes
1answer
434 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?
12
votes
1answer
323 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 ...
0
votes
1answer
110 views
Difference between $(a|b)^\ast$ and $a^\ast b^\ast$?
What is the difference between $(a|b)^\ast$ and $a^\ast b^\ast$? Can you show more examples of Kleene star and patterns and explain a little bit? I've searched so many sites in Google, but it returns ...
