Given context-free grammar
\begin{align*}
&S \to M \;|\; XN \;|\; W \;|\; 0N \;|\; 1Z1 \\
&M \to 0M0 \;|\; N \\
&N \to N0 \;|\; 0 \\
&W \to 0W \;|\; 00W0 \\
&X \to 0X1 \;|\; 0 \;|\; 0Y0 \\
&Z \to W \;.
\end{align*}- Is
$V$ ambiguous? - Give a normalized grammar equivalent to
$V$ .
It is easier to normalize the grammar first and then to look for ambiguities, thus the answers are in reverse order.
- Any derivation containing
$W$ cannot terminate, and so does$Z$ . - Further, we can eliminate the rule
$M → N$ . -
$Y$ has no derivation rules, thus we can also remove it.
Thus obtaining:
\begin{align*}
&S \to M \;|\; XM \;|\; 0M \\
&M \to 0M0 \;|\; 0 \;|\; 0M \\
&X \to 0X1 \;|\; 0 \;.
\end{align*}- It is easy to see that
$M$ derives number of zeros greater than one, thus$M → 0M0$ is redundant. Subsequently,$S → 0M$ is already covered by$S → M$ .
What remains is:
\begin{align*}
&S \to M \;|\; XM \\
&M \to 0 \;|\; 0M \\
&X \to 0 \;|\; 0X1 \;.
\end{align*}Now it is easy to see that the string 00 can be derived in two different ways:
-
$S → M$ ,$M → 0M$ ,$M → 0$ . -
$S → XM$ ,$X → 0$ ,$M → 0$ .
Hence
Given context-free grammar
\begin{align*}
&S \to 0W11 \;|\; 0X1 \;|\; 0Y \\
&W \to S \;|\; Z \\
&X \to S \;|\; W \\
&Y \to 1 \\
&Z \to X \;.
\end{align*}- Bring
$V$ to Chomsky’s normal form. - What is the language of
$V$ ?
- We can easily eliminate
$Y$ variable, thus removing$Y → 1$ rule, and adding$S → 01$ rule. - We can eliminate
$Z$ variable by removing$Z → X$ and$W → Z$ rules and adding$W → X$ rule. - We can eliminate
$X$ variable by removing$X → S \;|\; W$ and$S → 0X1$ rules, and adding:$S → 0S1$ rule. - Finally, we can eliminate
$W$ variable by removing$W → S$ and$S → 0W11$ rules and adding$S → 0S11$ rule.
The resulting grammar will be:
\begin{align*}
&S \to 0S11 \;|\; 0S1 \;|\; 01 \;.
\end{align*}Since this is still not CNF, I introduce an extra variable:
\begin{align*}
&S \to XZ \;|\; 01 \\
&X \to 0 \\
&Y \to 1 \;|\; 11 \\
&Z \to SY \;.
\end{align*}Which is in CNF.
Using the results from the previous answer it is easy to see that
the language
Build a PDA accepting the language
\begin{align*}
L = \{ a^{i_1}b^{j_1}a^{i_2}b^{j_2}\dots a^{i_m}b^{j_m}
&\;|\; m \geq 1 \\
&\;|\; \forall k: i_k \geq j_k \geq 1 \\
&\;|\; \exists k: i_k > j_k \}
\end{align*}First, I’ll write the grammar for
\begin{align*}
&S \to aSb \;|\; K \;|\; SS \\
&K \to aKb \;|\; aaXb \\
&X \to aXb \;|\; aaXb \;|\; \epsilon \;.
\end{align*}-
$X$ generates strings of the form$\{ a^nb^m \;|\; n \geq m \}$ . - Similarly,
$K$ generates strings of the form$\{ a^nb^m \;|\; n > m \}$ . - The derivatin of
$S$ can only terminate when it eventually derives$K$ . It can repeat as many times as needed to accept the entire string. Where the repeated element is, again, of the form of either$\{ a^nb^m \;|\; n \geq m \}$ , or$\{ a^nb^m \;|\; n > m \}$ .
Thus, at least informally, we are convinced the grammar generates
Now, the automaton:
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
semithick]
\node[initial,state] (A) {$q_0$};
\node[state] (B) [right of=A, above of=A] {$q_1$};
\node[state] (C) [right of=B, below of=B] {$q_2$};
\node[state] (D) [below of=A] {$q_3$};
\node[state] (E) [right of=D] {$q_4$};
\node[state] (F) [right of=E] {$q_5$};
\node[accepting,state] (G) [below of=E] {$q_6$};
\node[state] (H) [left of=G, below of=G] {$q_7$};
\node[state] (J) [right of=G, below of=G] {$q_8$};
\path (A) edge node {$a, \epsilon \to A$} (B)
edge node {$\epsilon$} (D)
(B) edge [loop above] node {$a, A \to AA$} (B)
edge node {$\epsilon$} (C)
(C) edge [loop above] node {$b, A \to \epsilon$} (C)
edge node {$b, Z \to \epsilon$} (A)
(D) edge node {$a, A \to AA$} (E)
(E) edge [loop above] node {$a, A \to AA$} (E)
edge node {$\epsilon, A \to \epsilon$} (F)
(F) edge [loop above, align=center] node {
$b, A \to \epsilon$ \\
$\epsilon, A \to \epsilon$} (F)
edge node {$b, Z \to \epsilon$} (G)
(G) edge node {$\epsilon$} (H)
(H) edge [loop below] node {$a, A \to AA$} (G)
edge node {$\epsilon$} (J)
(J) edge [loop below, align=center] node {
$\epsilon, A \to \epsilon$ \\
$b, A \to \epsilon$} (J)
edge node {$\epsilon, Z \to \epsilon$} (G);
\end{tikzpicture}The idea behind this diagram is as follows:
- Loop as many times as needed (possibly zero) over strings
$a^nb^n$ , where$n \geq 1$ . - Nondeterministically parse a string
$a^nb^m$ where$n > m$ . - Loop as many times as needed (possibly zero) over strings
$a^nb^m$ where$n \geq m$ . - Before accepting state, keep discarding
$A$ until none remain for as long as you don’t see an$a$ . - Accept the string.
Construct a PDA for
\begin{align*}
L = \{ dw_1dw_2d\dots w_nd
&\;|\; n \geq 3 \\
&\;|\; \forall k: w_k \in \{a,b,c\}^* \\
&\;|\; \exists k: 1 \leq k \leq n - 2 \land \abs{w_k} = \#_c(w_{k+2}) \}
\end{align*}The automaton for
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
semithick]
\node[initial,state] (A) {$q_0$};
\node[state] (B) [right of=A] {$q_1$};
\node[state] (C) [below of=B] {$q_2$};
\node[state] (D) [left of=C] {$q_3$};
\node[state] (E) [left of=D] {$q_4$};
\node[state,accepting] (F) [left of=A] {$q_5$};
\node[state] (G) [above of=F] {$q_6$};
\path (A) edge node {$d$} (B)
(B) edge [loop above] node {$a,b,c,d$} (B)
edge node {$d, \epsilon \to Z$} (C)
(C) edge [loop right, align=center] node {
$a, A \to AA$ \\
$b, A \to AA$ \\
$c, A \to AA$} (C)
edge node {$d$} (D)
(D) edge [loop above] node {$a,b,c$} (D)
edge node {$d$} (E)
(E) edge [loop left] node {$c, A \to \epsilon$} (E)
edge node {$d, Z \to \epsilon$} (F)
(F) edge node {$a,b,c$} (G)
(G) edge [loop left] node {$a,b,c$} (G)
edge node {$d$} (F);
\end{tikzpicture}(Whenever stack symbols neither read, nor added nor removed, they are omitted from the diagram to make it easier to read)
The rationale for this diagram is as follows:
- Read the first
$d$ . - Keep reading as many of
$as$ ,$bs$ ,$cs$ or$ds$ as necessary. - Non-deterministically, upon reading
$d$ assume reading the “special” sequence of$as$ ,$bs$ and$cs$ , which must be equal in length to the sequence of$cs$ to follow after. “Notice” this event by pushing$Z$ on stack. - Read
$as$ ,$bs$ and$cs$ pushing$As$ on stack. - Read
$d$ . - Read any number of
$as$ ,$bs$ or$cs$ . - Upon reading
$d$ start reading$cs$ while discarding$As$ . - Once you pop
$Z$ you also must read$d$ , this will ensure the number of$cs$ is the same as the number of$as$ ,$bs$ and$cs$ , read in step (4). - After this had happened, we’ve already found the “special” substring,
now we just need to make sure to terminate when we read
$d$ .
Given language $L=\{a^kb^ic^jdj-ie^k \;|\; 1 \leq i \leq j, k \geq 2 \}$ build a deterministic PDA accepting it.
First, to better understand the language, I’ll give its grammar:
\begin{align*}
&S \to aaXbb \\
&X \to aXb \;|\; YZ \\
&Y \to bYc \;|\; bc \\
&Z \to cZd \;|\; \epsilon \;.
\end{align*}Informally, the language consists of three “major chunks”:
- An even number of
$as$ and$es$ on the edges (which also, eventually, must be longer than four). - The middle “chunk” is split into two parts:
- An even number of
$bs$ and$cs$ , necessarily more than two characters long. - Followed by the optional third “chunk” of an even number of
$cs$ and$ds$ .
- An even number of
Having realized this, we are now equipped to build an automaton:
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,
semithick]
\node[initial,state] (A) {$q_0$};
\node[state] (B) [right of=A] {$q_1$};
\node[state] (C) [right of=B] {$q_2$};
\node[state] (D) [below of=A] {$q_3$};
\node[state] (E) [right of=D] {$q_4$};
\node[state] (F) [right of=E] {$q_5$};
\node[state,accepting] (G) [right of=F] {$q_6$};
\path (A) edge [loop above, align=center] node {
$a, A \to AA$ \\
$a, Q \to AQ$ \\
$a, \epsilon \to Q$} (A)
edge node {$b, A \to BA$} (B)
(B) edge [loop above] node {$b, B \to BB$} (B)
edge node {$c, B \to \epsilon$} (C)
(C) edge [loop above] node {$c, B \to \epsilon$} (C)
edge node {$c, A \to BA$} (D)
edge node {$e, A \to \epsilon$} (F)
(D) edge [loop above] node {$c, B \to BB$} (D)
edge node {$d, B \to \epsilon$} (E)
(E) edge [loop below] node {$d, B \to \epsilon$} (E)
edge node {$e, A \to \epsilon$} (F)
(F) edge [loop below] node {$e, A \to \epsilon$} (F)
edge node {$e, Q \to \epsilon$} (G);
\end{tikzpicture}In words, this automaton can be described as:
- Read an
$a$ and put$Q$ on stack. - Read another
$a$ and put$A$ on stack (this is to satisfy$\abs{a^k} \geq 2$ .) - Keep reading
$as$ . While you read$as$ push$A$ on the stack. - Once you read
$b$ , start pushing$Bs$ on the stack. - Once you read
$c$ , start popping$Bs$ from the stack. - Once no
$Bs$ remain on the stack, if you read$c$ , this means$j > i$ , keep reading$cs$ while pushing$Bs$ on the stack.- When you encounter
$d$ , you need to stard popping$Bs$ from the stack. - Once you read
$d$ , but you see$A$ on the stack, move to (8).
- When you encounter
- Otherwise,
$i = j$ , hence you must be reading$d$ . Skip to the next state. - Now you must be reading
$e$ . Keep reading$es$ as long as there are$As$ on the stack. - Once you encounter
$Q$ on the stack, this is also the final$e$ . If the input ends here, you are done!
Given PDA
Informally, all we need to do is to add transitions between the accepting
states and the initial state of
More formally, let
Then,
\begin{align*}
\delta_n = \delta \cup
\{&(q_n, \epsilon, \gamma \in \Gamma \setminus \{Z\}, q_n, \epsilon), \\
&(q_n, \epsilon, Z, q_0, Z), \\
&(q_f \in F, \epsilon, \gamma \in \Gamma \setminus \{Z\}, q_n, \epsilon), \\
&(q_f \in F, \epsilon, Z, q_0, Z)\}
\end{align*}reading as: when in state