# Tagged Questions

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

43 views

### Is the Champernowne constant an automatic number?

The Champernowne constant in base $b \geq 2$ is obtained by concatenating the $b$-ary expansion of every integer. For example, in base $10$ this is $$0.123456789101112131415\dotsc$$ Question: Is the ...
22 views

### Why Petri Net tokens are not added?

Reading this article it says: A firing of an enabled transition removes one token from each input place and adds one token to each output place. Now if I have the following net, with all ...
19 views

69 views

### Where is my mistake in this DFA minimization?

I'm currently having trouble minimizing my DFA. I have the following graph: (ignore the numbers after ":") Using the table minimization method I reached: (x is distinguishable, O is ...
254 views

### How to prove the language of all binary numbers that are prime is nonregular using pumping lemma?

How to prove the language of all binary numbers that are prime is not regular using pumping lemma? I have seen Can an infinite set of primes be a regular language or CFG? We have not studied the ...
262 views

### how to prove that the following is not a regular language?

the language we want to disprove is : $$L = \{ 0^i1^j| gcd(i,j)=1 \}$$ my attempt : i used the pumping lemma this way: consider the set of strings of the form $0^p1^q$ such that $n <=p$ and ...
64 views

### Show that language $L'$ is regular given $L$ is regular

I show you some solution and I ask you for looking at it. $L'=\{y|\exists_{z,x} xyz\in L\wedge |x|=|y|=|z|\}$ Automaton for language $L$: $M=(Q,\Sigma, \delta, q_0, F)$ For language $L':$ \$M'=(Q', ...