Week5

Term	Typical symbol	Meaning
	or Notation
Context-free grammar (CFG)	$G$	$G = (V, \Sigma, R, S)$
The set of variables	$V$	Finite set of symbols that represent phases in production pattern
The set of terminals	$\Sigma$	Alphabet of symbols of strings generated by CFG
		$V \cap \Sigma = \emptyset$
The set of rules	$R$	Each rule is $A \to u$ with $A \in V$ and $u \in (V \cup \Sigma)^*$
The start variable	$S$	Usually on left-hand-side of first/ topmost rule

Derivation	$S \Rightarrow \cdots \Rightarrow w$	Sequence of substitutions in a CFG (also written $S \Rightarrow^* w$). At each step, we can apply one rule to one occurrence of a variable in the current string by substituting that occurrence of the variable with the right-hand-side of the rule. The derivation must end when the current string has only terminals (no variables) because then there are no instances of variables to apply a rule to.
Language generated by the context-free grammar $G$	$L(G)$	The set of strings for which there is a derivation in $G$. Symbolically: $\{ w \in \Sigma^* \mid S \Rightarrow^* w \}$ i.e. \[\{ w \in \Sigma^* \mid \text{there is derivation in $G$ that ends in $w$} \}\]
Context-free language		A language that is the language generated by some context-free grammar

Examples of context-free grammars, derivations in those grammars, and the languages generated by those grammars

$G_1 = (\{S\}, \{0\}, R, S)$ with rules \[\begin{aligned} &S \to 0S\\ &S \to 0\\ \end{aligned}\] In $L(G_1)$ …

$G_2 = (\{S\}, \{0,1\}, R, S)$ \[S \to 0S \mid 1S \mid \varepsilon\] In $L(G_2)$ …

$(\{S, T\}, \{0, 1\}, R, S)$ with rules \[\begin{aligned} &S \to T1T1T1T \\ &T \to 0T \mid 1T \mid \varepsilon \end{aligned}\]

$G_4 = (\{A, B\}, \{0, 1\}, R, A)$ with rules \[A \to 0A0 \mid 0A1 \mid 1A0 \mid 1A1 \mid 1\] In $L(G_4)$ …

Wednesday: Context-free languages

Warmup: Design a CFG to generate the language $\{a^i b^j \mid j \geq i \geq 0\}$

Theorem 2.20: A language is generated by some context-free grammar if and only if it is recognized by some push-down automaton.

Definition: a language is called context-free if it is the language generated by a context-free grammar. The class of all context-free language over a given alphabet $\Sigma$ is called CFL.

Suppose $L_1$ and $L_2$ are context-free languages over $\Sigma$. Goal: $L_1 \cup L_2$ is also context-free.

Let $M_1 = ( Q_1, \Sigma, \Gamma_1, \delta_1, q_1, F_1)$ and $M_2 = ( Q_2, \Sigma, \Gamma_2, \delta_2, q_2, F_2)$ be PDAs with $L(M_1) = L_1$ and $L(M_2) = L_2$.

Let $G_1 = (V_1, \Sigma, R_1, S_1)$ and $G_2 = (V_2, \Sigma, R_2, S_2)$ be CFGs with $L(G_1) = L_1$ and $L(G_2) = L_2$.

Suppose $L_1$ and $L_2$ are context-free languages over $\Sigma$. Goal: $L_1 \circ L_2$ is also context-free.

Let $M_1 = ( Q_1, \Sigma, \Gamma_1, \delta_1, q_1, F_1)$ and $M_2 = ( Q_2, \Sigma, \Gamma_2, \delta_2, q_2, F_2)$ be PDAs with $L(M_1) = L_1$ and $L(M_2) = L_2$.

Let $G_1 = (V_1, \Sigma, R_1, S_1)$ and $G_2 = (V_2, \Sigma, R_2, S_2)$ be CFGs with $L(G_1) = L_1$ and $L(G_2) = L_2$.

iff it is described by some regular expression
iff it is recognized by some DFA
iff it is recognized by some NFA

iff it is generated by some CFG
iff it is recognized by some PDA

\[\begin{aligned} &\{ a^n b^n c^n \mid 0 \leq n , n \in \mathbb{Z}\}\\ &\{ a^i b^j c^k \mid 0 \leq i \leq j \leq k , i \in \mathbb{Z}, j \in \mathbb{Z}, k \in \mathbb{Z}\}\\ &\{ ww \mid w \in \{0,1\}^* \} \end{aligned}\] (Sipser Ex 2.36, Ex 2.37, 2.38)

There is a Pumping Lemma for CFL that can be used to prove a specific language is non-context-free: If $A$ is a context-free language, there there is a number $p$ where, if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into five pieces $s = uvxyz$ where (1) for each $i \geq 0$, $uv^ixy^iz \in A$, (2) $|uv|>0$, (3) $|vxy| \leq p$. We will not go into the details of the proof or application of Pumping Lemma for CFLs this quarter.

Friday: Review

Week 5 at a glance

Textbook reading: Chapter 2

For Friday: Test 1 is Friday Feb 9 in discussion section 4pm-4:50pm WLH 2001. The test covers material in Weeks 1 through 4 and Monday of Week 5. To study for the exam, we recommend reviewing class notes (e.g. annotations linked on the class website, podcast, supplementary video from the class website), reviewing homework (and its posted sample solutions), and in particular *working examples* (extra examples in lecture notes, textbook examples listed in hw, review quizzes – PDFs now available on the class website, discussion examples) and getting feedback (office hours and Piazza).

Make sure you can:

TODO:

Review quizzes based on class material each day.

Test this Friday in Discussion section.