Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

3
votes
2answers
66 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
180 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
84 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
396 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
109 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
215 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
145 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
97 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
75 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 ...
9
votes
2answers
466 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
221 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
91 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
969 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
186 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
159 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 ...
3
votes
4answers
6k 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
67 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 ...
7
votes
3answers
5k 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
224 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
80 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
134 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 ...
3
votes
2answers
110 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
375 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
284 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
613 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
123 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
125 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
315 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
61 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
213 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
280 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
66 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
1answer
530 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
84 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
250 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
275 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
999 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?
14
votes
1answer
418 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
141 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 ...
0
votes
1answer
330 views

Is it always possible to convert a non-deterministic PDA to a deterministic one?

Is it always possible to convert a non-deterministic PDA to a deterministic one? What is the significance of this observation for the computing power of contex-free grammars?
2
votes
1answer
581 views

Turing Machine Vs Linear Bounded Automata

Example of language accepted by Turing Machine but not by Linear Bounded Automata ? Is there any EXPSPACE language?
7
votes
2answers
430 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
197 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 ...
0
votes
1answer
70 views

How many neighbours should a cell have in a cellular automata?

So, I'm currently working with cellular automata but I started to wandered, what's the perfect amount of neighbours each cell should have if I'm working in a bi-dimensional space? Up to now I was ...
0
votes
3answers
188 views

Word problem in a free group

Can the word problem in a free group be solved by a finite state automaton? I know it can be solved by a pushdown automaton.
4
votes
1answer
134 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 ...
1
vote
1answer
50 views

what is the effect of adding another stack to a PDA

does it increase the power of a push down automata? or does it have no effect on the power of the PDA ?
3
votes
2answers
519 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. ...
0
votes
2answers
482 views

String matching automata preprocessing

I have an alphabet A = {a,b,c} and a pattern P = "abcaab". The task is to build a finite automaton of the transition function (delta) for {0,6} (the length of the pattern) and each element of the ...
1
vote
2answers
69 views

Closure property of Alternating language

Problem Given a language $L$ is context-free, must $\operatorname{alt}(L)$ is also context free? where $$\operatorname{alt}(L) = a_1a_2a_3 \ldots, \quad L = a_1b_1a_2b_2a_3b_3 \ldots$$ I couldn't ...