# Tag Info

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 ...

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 ...

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

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

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 ...

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 ... 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 Here's a grammar. Terminals are lowercase. Nonterminals are uppercase. The starting symbol is$F.F=Gr^2G = pGb | HH = rHb | p$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 The easiest way to deal with$A$is to realize that it has a simpler description: $$A=\{u1v:u,v\in\Sigma^*\text{ and }|u|,|v|\ge 1\}\;.$$ Once you see this, it’s very easy to write down a context-free grammar for$A$. To show that$B$is not context-free, use the pumping lemma with the word$s=0^{p+2}10^p10^{p+2}$, where$p$is the pumping length. You’ll ... 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 = ...

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?

Only top voted, non community-wiki answers of a minimum length are eligible