New answers tagged automata
0
Two interesting properties: 1. There are states that have no predecessor. 2. Game of life is actually Turing complete!
3
I'd say it's "the most famous" cellular automaton, in the sense that the structures its rules generate have been studied and given names to.
One property that it does have, that makes it more interesting than other automata, is that stable structures are fairly common in Conway's game of life.
If you try and tweak the rules (by changing the ...
0
Yes, there are both deterministic and non-deterministic pushdown automata.
Non-determistic pushdown automatons can recognize all context-free languages, while deterministic pushdown automatons con only recognize a proper subset of the context-free languages (these languages are called deterministic context-free languages).
0
No. Represent your automata as a directed graph where each edge is labelled as a symbol of the alphabet. Then:
Reverse all edges.
Change the former initial state to an non-initial accepting state.
Add a new initial state $q_0$, and add a transition (edge) $q_0 \overset{\varepsilon}{\to}q$ towards every state (vertex) $q$ that formerly was an accepting state....
0
I could make this post of the answer because of comments of Hendrik Jan.
Thank you.
If we assume the input is given as $~ 111000 ~~~$,
The state is moved to $~ q_{1} ~$ without before input since $~ \epsilon_{} ~$ exists.
And after the arrival at $~ q_{1} ~$,$ is pushed at bottom of the stack.
Nextly the procedures of 111000 begin.
At first "1" ,...
0
Let's consider the language $L' = \{a^ib^j \mid i \ge 0, j \ge 1, \mbox{5 divides $2i+3j$}\}$ for a second. To design a DFA for $L'$ you can essentially keep a counter $x$ for $2i+3j$. This counter is stored modulo $5$.
The states of DFA will be all pairs $(x,y)$ with $x \in \{0,1,2,3,4\}$ and $y \in \{0,1\}$. Intuitively, $y=0$ will mean that we have not ...
3
From the supplied solution, it's clear that the question was written incorrectly. The fifth, sixth and seventh productions should produce $X$, $Y$ and $Z$, respectively, instead of $A$, $B$ and $C$. You might want to report this typo to whomever set the problem.
Once you make that change, the fact that it is equivalent to a right-linear grammar can be shown ...
1
actually you also had a mistake in the definition of the problem and I've considered its |Wa|=|Wb| or |Wa|=|Wc|.
Any way using non-deterministic I've tried to separate two conditions:
1
If you look at the formal definition of grammars, there is nothing requiring a nonterminal symbol to apppear in the left side of a production rule.
So $G$ is a perfectly valid grammar.
If we drop all useless production we are left with $S \to \lambda$. Therefore $L(G) = \{ \lambda\}$, which is a finite language and hence it is also regular. If you really ...
Top 50 recent answers are included
