# Tag Info

0

So yes, those are needed. Note that the transitions from q5, q3 and q1 that use these go to q8. Once you're in q8, there's no going back to any other state except q9. So those transitions mean that you've seen all your input and made them all upper case. Now it's time to convert them back to the original lower case. In dealing with TMs and other automata, ...

1

Here is one calculation (inspired by dtldarek's comment): Let $S_k$, $k=0,1,2$ represent the states above. We have the equations $S_1 = (0|1) \big | S_1 1 \big | S_2 1$, $S_2 = S_1 0 \big | S_2 0$. Solving for $S_2$ gives $S_2 = S_1 0 0^*$, then $S_1 = (0|1) \big | S_1 1 \big | S_1 0 0^* 1$, which reduces to $S_1 = (0|1) (1 | 0 0^* 1)^*$, and so $S_2 = ... 2 Yes, they are. You can simplify both to $$\Sigma^+\mathtt{0}$$ for$\Sigma = \{\mathtt{0},\mathtt{1}\}$, that is, $$(\mathtt{0}\cup\mathtt{1})(\mathtt{0}\cup\mathtt{1})^*\mathtt{0}$$ The crucial part is to observe that, after you cleared the initial state (i.e. read the first symbol), whatever you do, and wherever you are, after reading symbol$\mathtt{0}$... 2 I don't think there is a general approach. YMMV, but three things that helps me a lot are: You can think of CFLs as a complicated multi-parenthesis-languages. Finding this left-paren to right-paren corresponcence gives a sense of structure of that language. In your case$\mathtt{a}$plays the role of$(_c$and$(_b$, while$\mathtt{b}$and$\mathtt{c}$... 2 Here I would notice that if$b$and$c$were the same symbol, this language would be just$\{a^kb^k:k\ge 0\}$, which is generated by$S\to aSb\mid\epsilon$. However,$b$and$c$are not the same, so somehow instead of generating$b$s to the right of the$S$, I need to generate a mixture of$b$s and$c$s. If I didn’t care about their order, I could replace ... 0 An easy way to prove this result is to use the fact that a language is regular if and only if it is recognized by a finite monoid. Definition. A language$L$of$A^*$is recognized by a finite monoid$M$if there is a surjective monoid morphism$f:A^* \to M$and a subset$P$of$M$such that$f^{-1}(P) = L$. Let now$K = \{u \in A^* \mid u^3 \in L\}$and ... 0 S -> NM N -> aNb | epsilon M -> cMd | epsilon 0 Hint. Assume that you have a DFA for$L'$whose set of states is$Q$and transition rule$\delta_1$. Now construct a new DFA whose set of states is$\mathcal P(Q\times Q)$and transition rule $$\delta_2(X,a) = \{ (q,\delta_1(q',a)) \mid (q,q') \in X\}$$ Now, an appropriate choice of initial and accepting states will solve your problem. 2 Suppose that$M=\langle Q,\Sigma,\delta,q_0,F\rangle$is a DFA that recognizes$L'$; we can construct a DFA$M'=\langle Q',\Sigma,\delta',q_0',F'\rangle$that recognizes$L$as follows.$Q'$is the set of all functions from$Q$to$Q$. A state$f\in Q'$is an acceptor state in$M'$if$f^3(q_0)\in F$, where$f^3(q)=f(f(f(q)))$; i.e.,$F'=\{f\in ...

2

Here’s a fairly systematic way to approach such problems, at least when the grammar is relatively simple. Note first that you must begin with $S\to 1S$ or $S\to 00A$. Once you apply the latter production, however, you can never apply the first. Thus, any derivation must start with some number $m\ge 0$ of applications of $S\to 1S$ followed by an application ...

0

It looks like the language is $1^{*}000(0)^{*}$. Notice we can have no $1$'s present; and if we do, we can keep revisiting $S$. To terminate, we need to visit the $S \to 00A$ rule to get to the $A$ rules. Then we can keep tacking on $0$'s or terminate with one additional $0$.

0

Try to analice the language you want to build a PDA for. Have you seen the standard example for the language $\{a^nb^n\mid n\in\mathbb N\}$? (I guess this should be in the book you cite.) What would you do to implement a PDA for this simpler example? What are the states and what is the role of the stack in this example (it is used to store $a$'s so you can ...

0

I gave an explanation for constructing a PDA here. A pushdown automaton is a a finite state machine with a stack. So can you design an algorithm where the only memory is the stack? 1) The usage of the stack comes into play in making sure the number of $a$'s and $b$'s are the same. So read in the $a$'s and push them onto the stack. For each ...

2

The first and biggest problem is that you haven’t answered the question: it asks for pushdown automata accepting the languages $L_1$ and $L_2$, but you’ve attempted to give context-free grammars generating the languages; that’s a different thing altogether. Your context-free grammars are in any case very far from generating the languages in question. Your ...

1

A pushdown automaton is a a finite state machine with a stack. So can you design an algorithm where the only memory is the stack? I would do it as follows. If the first character is not a $p$, reject the string. Otherwise, begin pushing the $p$'s onto the stack. Once you read in an $r$, transition the state and push each $r$ onto the stack. Once you finish ...

1

Here's a grammar. Terminals are lowercase. Nonterminals are uppercase. The starting symbol is $F.$ $F=Gr^2$ $G = pGb | H$ $H = rHb | p$

1

Two states are equivalent if they accept the same language. An equivalence class is therefore a set of states that all accept the same language (and no other state in the automaton does). In particular in a minimal autommaton, all states accept different languages, so each state is alone in its equivalence class.

1

Hint: Let $M_y$ be the automaton that recognizes suffixes from $L$ and $M_x$ be the automaton that recognizes prefixes from $L$. Neither automaton has any transitions on $Z$, since $Z\notin\Sigma$. Could you connect $M_y$ to $M_x$ somehow, and let $M_y$ recognize the $y$ part of the input string, and $M_x$ recognize the $x$ part?

Top 50 recent answers are included