# Tagged Questions

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

117 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 ...
209 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 ...
64 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$ ...
127 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 ...
82 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 ...
330 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 ...
97 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 ...
199 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 ...
139 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 ...
92 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 ...
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 ...
380 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 ...
199 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 ...
77 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 ...
684 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 ...
157 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 ...
142 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 ...
4k views

120 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 ...
117 views

207 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. ...
219 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 ...
823 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?
379 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 ...
128 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 ...
269 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?
451 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?
400 views

193 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 ...
67 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 ...
161 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.
131 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 ...