assignment-17.org

Assignment 17, Authomata Theory

Problems

Problem 1

Prove that language $L = \{a^ib^i+jc^j \;|\; 1 \leq i \leq j\}$ is not context-free.

Answer 2

Suppose, for contradiction, $L$ is context-free, then, according to pumping lemma, the following applies:

1. $p$ is the “pumping length”.
2. For every word $z ∈ L$, $z = uvwxy$, s.t.
3. $\abs{vwx} \leq p$.
4. $\abs{vx} \geq 1$.
5. $uv^nwx^ny ∈ L$.

Consider $p = i$, then there are five distinct ways to decompose $w$ into $uvwxy$. Of them three will decompose in a way such that both $v$ and $x$ are the same symbol, i.e. both $v$ and $x$ are either $a$, $b$ or $c$.

It is easy to see none of the above can be pumped: if $v = a^r$ and $x = a^s$ then by pumping $a$, eventually there will be more $as$ in $z$ than $cs$, which contradicts $i \leq j$. Similarly, if we pump $bs$, eventually there will be more $bs$ than $as$ and $cs$ together. Similarly for $cs$.

Another two possible decompositions are:

1. $v = a^r$ and $x = b^s$. However, again, if we pump $as$, i.e. $r ≠ 0$, then eventually there will be more $as$ than $cs$. And similarly for $bs$. When we pump $as$ and $bs$ together, eventually there will be more $as$ than $cs$, again, contradicting $i \leq j$.
2. Thus the only case worth considering is where $v = b^r$ and $x = c^s$. Consider the word $z = a^pb^2pc^p ∈ L$ with this decomposition. If either $r = 0$ or $s = 0$, we proceed as above, however, if $r = s ≠ 0$, then it must be the case that for all words $z’ = a^pb^p+p-r+r*ic^p-r+r*i$, $z’ ∈ L$. but it is not the case for $i=0$. Since $\abs{a^p} > \abs{c^p-r}$ contrary to the required $i \leq j$.

These are all the possible decompositions of $z$, since neither can be pumped, it must be the case that $L$ is not context-free.

Problem 2

Prove that context-free languages are not closed under $max$ operation.

Answer 2

Recall the definition of $max$:

\begin{align*}
  max(L) = \{u \in L \;|\; \forall v \in \Sigma^*: uv \in L \implies v = \epsilon\} \;.
\end{align*}

Let’s take $L = \{a^nb^mc^k \;|\; n \leq k ∨ m \leq k\}$. $L$ is context-free, since we can give a context-free grammar $L(G) = L$ as follows:

\begin{align*}
  &S \to X \;|\; Y \\
  &X \to aXC \;|\; C \\
  &C \to bCc \;|\; Cc \;|\; bBCc \;|\; c \\
  &B \to bB \;|\; b \\
  &Y \to AZ \\
  &A \to aA \;|\; \epsilon \\
  &Z \to bZc \;|\; Q \\
  &Q \to cQ \;|\; c \;.
\end{align*}

However, the $max(L) = \{a^nb^nc^n\}$, which is known to be non-context-free.

Problem 3

Prove $L = \{a^ib^2c^j \;|\; i = 2j\}$ is constext free using closure properties and some language from assignment 16.

Answer 3

Recall that we proved language $M = \{a^kb^ic^jd^j-ie^k \;|\; 1 \leq i \leq j, k \geq 2\}$ to be context-free. We can define homomorophism:

\begin{equation*}
  h(x) = \begin{cases}
    aa &\for x=a \\
    b &\for x=b \lor x=c \lor x=d \\
    c &\for x=e
  \end{cases} \;.
\end{equation*}

Now, $M’ = h(M) = \{a^2kb^i+j+j-ic^k\}$, where $2j$ is any even integer, thus could be rewritten as $\{a^2kb^2jc^k\}$. Due to closure of context-free languages under homomorphism, $M’$ is context-free.

Next, we can intersect $M’$ with a regular language $a^*b^2c^*$ to get $L$. Since context-free languages are closed under intersection with regular languages we proved that $L$ is context-free.

Problem 4

Prove or disprove each of the following statements:

1. $L$ is a irregular context-free language. $G$ is a context-sensitive language. $L ∩ G$ is not context-free.
2. $L_1$ and $L_2$ are irregular context-free languages s.t. $L_1 ∩ L_2 ≠ ∅$. $L_1 ∩ L_2$ is irregular context-free language.
3. $L$ is a regular language over $Σ$. $G$ is a context-sensitive language. Define substitution $f$ s.t. $∀ σ ∈ Σ: f(σ) = G$. $f(L)$ is context-sensitive.

Anwser 4

An interesection of a context-free and a context-sensitive languages may be context-free. For instance, $\{a^nb^n\} ∩ \{a^nb^nc^n\} = \{a^nb^n\}$, where $n \geq 0$ is context-free.

Answer 5

An interesection of two context-free languages isn’t necessarily irregular. For instance $\{a^nb^n\} ∩ \{a^nc^n\} = \{a^n\}$ where $n \geq 0$ is regular.

Answer 6

The language $L = \{ε\}$ is regular. $f(L) = L$ since no substitution took place, hence this claim is false.

Problem 5

Let $L$ be a context-free language over the alphabet $Σ = \{a,b,c,… z\}$. Prove that $L’$ is also context-free, when defined as follows:

\begin{align*}
  L' = \{w \;|\; \abs{w} \equiv 0 \pmod{2}
                 \;\land\; \abs{w} \geq 4 
                 \;\land\; \textbf{Sub}(w)\}
\end{align*}

Where $\textbf{Sub}(w)$ is true whenever

\begin{equation*}
  w = \begin{cases}
    x\textbf{a}y\textbf{z}z &\for xpyqz \in L 
                             \land p \neq \textbf{a}
                             \land q \neq \textbf{z} \\

    x\textbf{z}y\textbf{a}z &\for xpyqz \in L 
                             \land p \neq \textbf{z}
                             \land q \neq \textbf{a}
  \end{cases} \\
  \abs{p} = \abs{q} = 1
\end{equation*}

Answer 7

1. Provided $L$ is regular, we can bring its grammar $G$ to Greibach normal form.
2. Now, for every rule of the form $A → xA_1A_2A_3… A_n$ we introduce new rules: $A → aA’_1A’_2A’_3… A’_n$ whenever $x ≠ a$ and $A’ → zA”_1A”_2A”_3… A”_n$ whenever $x ≠ z$.
3. We replace the rules of the form $A → x$ with $A” → x$.

The resulting grammar $G’$ will nondeterministically substitute $a$ for some terminal, which does not equal $a$ and $z$ for some terminal which does not equal $z$. It can only terminate the derivation when both substitutions took place. Using the same technique we can construct grammar $G”$ which first replaces $z$ and then $a$. The union of $G’$ and $G”$ (still a context-free grammar, since context-free languages are closed under union) will take care of $\textbf{Sub}(w)$ condition.

Now, we can take $G”’ = (G’ ∪ G”) ∩ R$, where $R = \{r \;|\; r ∈ Σ^+ ∧ \abs{r} \geq 4\}$. Since $R$ is regular, and intersection of context-free and regular languages is known to be context-free, $G”’$ must be context-free. This completes the proof.