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{align*} S_{A} &\to D S_{A} D \mid 0 \ D &\to 0 \mid 1 \end{align*}
(this is for generating odd palindromes with range{0,1} and middle symbol 0) **And for $B$:**S_{B} \to 0 S_{B} 1 S_{B} \mid 1 S_{B} 0 S_{B} \mid \epsilon
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{align*} S &\to S_{A} S_{B} \ S_{A} &\to DS_{A}D \mid 0 \ D &\to 0 \mid 1 \ S_{B} &\to 0 S_{B} 1 S_{B} \mid 1 S_{B} 0 S_{B} \mid \epsilon \end{align*}
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 $\epsilon$ 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^{*}$, 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{align*} A &\to DAD \mid 0 \ D &\to 0 \mid 1 \end{align*}
We can define $T$ with the following production in order to get $A^{*}$:T \to AT \mid \epsilon
This would result in a supposed string in $A^{*}$ being either empty or an $A$-string that has been concatonated with an additional string from $A^{*}$. This results in a final possible grammar for $A^{*}$:\begin{align*} T &\to AT \mid \epsilon \ A &\to DAD \mid 0 \ D &\to 0 \mid 1 \end{align*}
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. ![[Screenshot 2025-03-18 at 11.43.00 PM.png|sipser example]] *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 ![[problem-05-state-diagram.png]]