Homework 3 - Context Free Grammars

Abstract:

This document serves to answer the questions provided by the homework using CFG constructions and derivations, demonstrating the understanding of the concepts.

---

Problem 01

Consider the CFG

\begin{align*}

S &\to AB \mid C \

A &\to aAb \mid ab \

B &\to cBd \mid cd \

C &\to aCd \mid aDd \

D &\to bDc \mid

\end{align*}

> > Give the leftmost derivations for the string **aabbccdd** We start with the **1st Derivation** using $S \to AB$: 1. Beginning: $S$ 2. Apply $S \to AB$: $S\Rightarrow AB$ 3. Expand left nonterminal $A \to aAb$: $AB \Rightarrow aAbB$ 4. New left nonterminal $A$ in string, replace with $A\to ab$: $aAbB \Rightarrow aabbB$ 5. expand left nonterminal $B$ with $B\to cBd$: $aabbB \Rightarrow aabbcBd$ 6. expand remaining $B$ with $B \to cd$: $aabbcBd \Rightarrow aabbccdd$ This becomes:

aabbccdd

**2nd Derivation**: 1. Beginning: $S$ 2. Apply $S \to C$: $S\Rightarrow C$ 3. Expand left nonterminal $C \to aCd$: string becomes $aCd$ 4. expand left nonterminal (middle $C$) $C \to aDd$: $aCd \Rightarrow a(aDd)d$ 5. using $D \to bDc$: $aaDdd \Rightarrow aa(bDc)dd$ 6. using $D \to bDc$ for left nonterminal D again: $aabDcdd \Rightarrow aab(bDc)cdd$ 7. Expanding $D$ with empty production $D \to \epsilon$: $aabbDccdd \Rightarrow aabb\epsilon ccdd$ This becomes:

aabbccdd

as required $\square$ --- ## Problem 02 > Produce a context-free grammar which generates the _complement_ of the language $L = \{ a^{n}b^{n} \mid n \geq 0 \}$ > > Hint: First write out $\bar{L}$(the complement of $L$) in set builder notation. You'll find it naturally decomposes into the union of two languages. If $L$ is:

L = { a^{n}b^{n}:n\geq 0}

The complement is(given $\Sigma = \{ a,b \}$):

\bar{L} = { w \in { a,b }^{*}: w \notin L }

This means that when a string $w$ is in $L$ when: - number of $a$'s is equal to number of $b$'s - $w$ is of form $a^{*}b^{*}$ Which means that a string $w$ is in $\bar{L}$ when: - it is NOT of the form $a^{*}b^{*}$ - it is of the form $a^{i}b^{j}$ where $i \neq j$ we can write this out as:

\bar{L} = { w \in { a,b }^{}:w \ is \ not \ in \ a^{}b^{*} } \cup { a^{i}b^{j}:i,j \geq 0 \ and \ i \neq j }

now lets construct a proper symbol $S$ ### Grammar Construction of $S$ We define $S$ as a start symbol with 3 options: - $A$: generate strings of form $a^{i}b^{j}$, where $i > j$ - $B$: generate strings of form $a^{i}b^{j}$ where $i<j$ - $C$: generate strings not of form $a^{*}b^{*}$, aka when contains substring $ba$ Defining a CFG:

\begin{align*}

S &\to A \mid B \mid C \

A &\to aAb \mid a \

B &\to aBb \mid b \

C &\to XbaY \

X &\to \epsilon \mid aX \mid bX \

Y &\to \epsilon \mid aY \mid bY

\end{align*}

This CFG works because: - $A$ generates with $a^{*}b^{*}$, but with too many $a$'s, which can balance a later b for a production - $B$ generates with $a^{*}b^{*}$ but with too many $b$'s, which pairs an a with a b for production, etc - $C$ generates for when it is not of the form $a^{*}b^{*}$, the production guarantees the string includes $ba$ Thus, we have created a grammar that generates the strins in $\{ a,b \}^{*}$ that are not of the form $a^{n}b^{n}$ as required $\square$ --- ## Problem 03 > Let $A$ be the language generated by the following context-free grammar: > >

\begin{align*} S &\to DSD \mid 0 \ D &\to 0 \mid 1 \end{align*}

> > and let $B$ be the language generated by: > >

S \to 0S1S \mid 1S0S \mid \epsilon

Produce a context-free grammar that generates the language $A \circ B$, where $\circ$ denotes the concatenation operation.

Given:

$$A\circ B=\{uv\mid u\in A,v\in B\}$$

We can find a grammar by combining the grammar definitions for $A$ and $B$.

We can do this by introducing a new start symbol that operates by generating a string for $A$ first and then the one from $B$.

We will define this symbol as $S$, where $S_A$ is for $A$ and $S_B$ is for $B$

Doing this for $A$:

$$\begin{array}{rl}{S}_A& \to D{S}_{A}D\mid 0\\ D& \to 0\mid 1\end{array}$$

(this is for generating odd palindromes with range{0,1} and middle symbol 0)

And for $B$:

$$S_B\to 0S_{B}1S_B\mid 1S_{B}0S_B\mid ϵ$$

which is responsible for the even length string (and equal num of 1 and 0) part of the grammar.

We are going to redefine a new start symbol $S$ again with:

$$S\to S_A{S}_B$$

(this is why we used the annotations $S_A$ and $S_B$)

With this we can generate the following acceptable grammar:

$$\begin{array}{rl}S& \to S_A{S}_B\\ S_A& \to D{S}_{A}D\mid 0\\ D& \to 0\mid 1\\ S_B& \to 0S_{B}1S_B\mid 1S_{B}0S_B\mid ϵ\end{array}$$

This works because:

• $S$ because its production ensures every string starts with piece from $A$ and then a piece from $B$
• $A$ works because the production of the nonterminal $S_A$ to add matching symbols on both ends of a string, while base case ensures palindrome is of odd length
• $B$ works because the production of nonterminal $S_B$ ensures that each step adds a 0 and a 1, while base case allows process to stop with $ϵ$

And thus this grammar generates the language $A\circ B$ as required $\square$

---

Problem 04

Given the context-free grammar generating $A$ in the previous problem, produce a context-free grammar that generates the language $A^{\ast }$, where * denotes the Kleene star operation.

We can do this by generating zero( or more ) strings from $A$.

We will once again define a new start symbol, but we will use $T$ this time as we already used $S$. $T$ will represent one or more copies of $A$.

With the grammer of $A$:

$$\begin{array}{rl}A& \to DAD\mid 0\\ D& \to 0\mid 1\end{array}$$

We can define $T$ with the following production in order to get $A^{\ast }$:

$$T\to AT\mid ϵ$$

This would result in a supposed string in $A^{\ast }$ being either empty or an $A$-string that has been concatonated with an additional string from $A^{\ast }$.

This results in a final possible grammar for $A^{\ast }$:

$$\begin{array}{rl}T& \to AT\mid ϵ\\ A& \to DAD\mid 0\\ D& \to 0\mid 1\end{array}$$

as required $\square$

---

Problem 05

A palindrome is a string that is the same when read forward or backward. Construct a PDA which recognizes $\{w\mid w=w^{\mathcal{R}}\}$ over the alphabet $\Sigma =\{0,1\}$.

Hint: Sipser gives an example in the textbook (2.18) which recognizes all even-length palindromes. You need only modify this machine so that it accepts odd- or even-length palindromes. A fully-labeled state diagram is all you need.

I found the Sipser example(see figure 01), although I am not sure if it is the right one. Regardless, I will be using that as a starting point.

We want to modify the PDA given by Sipser to handle both even and odd length palindromes.

Our approach will use:

• A push phase, as we read the inital half of string, we push symbols onto stack
• A transition to pop phase, at any point we try to guess that the middle of the string has been reached.
• pop phase, this will be for reading the second half of the string, where we will check that it matches the symbols being popped from the stack.
• accept, only iff the input has been consumed and stack is empty

This isn’t a difficult construction given the sipser example, so I wont be verbose.

Mermaid Diagram

can be a bit small, apologies

• q0: Start
• q1: Midpoint
• q2: Pop Phase
• qf: Accept