TOC ch2 slides notes toc

ToC_chapter_2_slides.pdf

• See ToC Syl CS3823 site, most important is class 21 nov 6th.
• See also TM_Remarks_TOC.pdf

Context Free Grammers (CFG)

Formal Def :Can be written as 5 tuple like ch1, but in this case it’s a 4 tuple varient: $(V,\Sigma ,R,S)$

1. V: set of vars
2. $\sum$: terminals (these are empty chars in result string)
3. set of rules, each being some var with string of vars + terminals (contains V and $\sum$)
4. $S\in V$ start variable

Language of the grammer:

$$\{w\in {\Sigma }^{\ast }|S\to w\}$$

Language Rules

Collection of substitution rules, aka productions. Denoted by some $G_1$ for example: for # being terminal (sometimes $ is used instead..)

$$\begin{array}{c}A\to 0A1\\ A\to B\\ A\to \#\end{array}$$

So if we had some G generating str 000#111, so our grammer would be:

$$L(G_1)=0^n\#1^n|n\ge 0$$

We can abbreviate multiple rules with the | symbol, so the original $G_1$ would become $A\to 0A_1|B|\#$

• yields: $uAv⟹v$
• Derives: $u{⟹}^{\ast }V$

Language to Grammer ex:

Say we hv: $0^n{1}^n\cup 1^n{0}^n$ then we can generate an $S\to S_1|S_2$ to denote the union. What if it was $\cap$? Result in $ as only string shared in both sets! (See slide 14)

CFG vs normal Grammer?

Normal grammers were as we knew for FAs in TOC ch1 slides notes toc. It doesn’t have memory like CFGs do with the stack. Generally denoted using multiple \to symbols instead of just strictly one.

A CFG may be ambiguous if its possible to get a different parse tree but same result string. For example $E\to E+E|id$ could result in a leftmost derivation (if we unwinded E to ID on the left first) or rightmost (OPA).

R/L-linear grammer + Linear Grammer

Regular and linear Grammer

regular grammar right/left-linear. non regular ex $A\to aBb$

linear grammar: at most one variable only one var can appear on the RHS

A regular grammar is always linear, but not all linear grammars are regular.

R/L-linear grammer is right-linear if all productions are of the form

$$\begin{array}{c}A\to xB\\ A\to x\end{array}$$

Then left would be:

$$\begin{array}{c}A\to Bx\\ A\to x\end{array}$$

Linear but not Regular

Consider the grammar

$$\begin{array}{c}S\to A\\ A\to aB\mid \lambda \\ B\to Ab\end{array}$$

This grammar is linear (only one variable per RHS) but it is not regular, because variables appear in mixed positions (sometimes left, sometimes right).

DFA TO CFG w/ normal lang? TODO..

Steps:

1. Generate var $R_i$ per q state in DFA
2. Add initial rule $a{R}_j$ to gen first production
3. Add $R_i\to a{R}_j$ and another $R_{i} \to $$ terminal
4. Add $R_0$ as start var (which would be $q_0$)

Chomsky Normal Form (CNF)

Simply, it’s a CFG that must follow the form:

$$\begin{array}{c}A\to BC\\ A\to a\end{array}$$

Note how it can’t hv the start symbol going to the RHS

• Each ONLY rule produces:
  • two non-terminal symbols (Strictly 2!!)
  • single terminal symbol
  • ONE instance of start_symbol $\to \lambda$

So if we needed to convert $A\to BCD$ we would need to create an intermediate rule like $A\to BX,X\to CD$

see also gfg Convert CFG to CNF

CFG → CNF Conversion

For a full example look at slide 24

States that all CFL is generated by CFG in CNF. When doing CNF, we need to elim rules frm the language. How? We create new rule s/t it doesn’t exist.

1. Add start var
2. elim A → $\lambda$ (this repeats, going up every level till it doesn’t exist, ensure replacement)
3. elim invalid rules eg. A → $B$ (loops till finishes, ensure to replace anything as needed)
   1. If we have A → B, then replace B with what it’s defined as, if its not possible, then its not a CNF

For part 2 take following example:

Removing ε-production

Deleting the first rule from:

$$\begin{array}{c}A\to \lambda \\ R\to uAvAw\end{array}$$

we go up one level (up to R from A) and input all possible combos

$$\begin{array}{c}R\to uvAw\\ R\to uAvw\\ R\to uvw\end{array}$$

Pumping Lemma for CFL

Pumping Lemma for CFL Steps:

1. Assume language is context-free, proceed towards contradiction
2. Choose candidate string $s\ge p$, $s=uvxyz$
3. Write out the conditions
   1. For each $i\ge 0$, $u{v}^{i}w{x}^{i}yz\in \text{language}$
   2. $|vy|>0$
   3. $|vxy|\le p$
4. Cover all cases of $vxy$

Finish off see slide 74…

Pushdown Automata PDAs

Similar to NFA but has stack for memory. Can recognize some non-regular langauges.

Formal Defition:

As usual we have a tuple, though its a 6 state tuple this time,

$$(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$$

1. $Q$ set of states
2. $\Sigma$ — input alphabet
3. $\Gamma$ — set of pushdown symbols (which can be pushed and popped from the stack) (isnt this just sigma with $ appended?)
4. $\delta$: defined as inp,pop→ push
5. $q_0\in Q$ — start state
6. $F\subseteq Q$ — accept states

$\nabla$ below means if read(1) ? pop 0 push $ Usually this is constructed after we make the PDA state diagram.

$$1,0\to \$$$

What if we had $\lambda$ instead of 0?

rule applies regardless of input! (We can always go to this) (confirm this..)

PDA Construction

Each delta follows inp,pop→ push. For a new state we push our current q, input (if we move to a blank location its $ϵ$ ), the inp is what we want to throw into the stack and pop is what’s replaced.

Formally, we can think of it as a bunch of if else statements;

• for start, begin in a $ϵ$, input

1. Arrow into start state $q_1$
2. $q_1$ into next state, usually push a $, inp + pop = $\lambda$
3. Generate rules

toc_PDA_ch2

Excalidraw Data

Text Elements

q1

q2

q3

b,a → \e

q4

\e,$→\e

\e,\e→$

\e,\e→\e

a,\e→a

\e,\e→\e

q5

q6

\e,\e→\e

b,\e→\e

c,a→\e

c,\e→\e

q7

\e,$→\e

top corrospond to i=j bottom i=k

Input: aabbccc

what I took away: generate NFA type graph. Create sample string (input below) go thru till die

The bottom copy always dies for bottom part,

• we always reject inp frm PDA
• bottom part esentially outputs the a^i b^j c

b/c 1 of 2 branches will accept, eventualyl will accept.

Embedded Files

8d809691ffa6a72362d832fa421eb4a196148a5b: Pasted Image 20251028123443_335.png

aef61d782dfacc9b9f27ed72c7fc4626b62ddff3: Pasted Image 20251028124838_831.png

Link to original

Example 18, Construct PDA from CFG

$$\begin{array}{c}S\to aTb|b\\ T\to Ta\lambda \end{array}$$

1. Create $ to denote end of stack
2. We then create some input S, with following loop states seen below

   example_18_toc_ch2.excalidraw

What does $ mean in PDAs?

The dollar sign is basically a tracker for the automata to know when it is done / all symbols have been popped out of the stack. It stays at the bottom of the stack and if the PDA reaches it, it knows it has reached the end of the string and can terminate.

nondeterministically guess vs guess

see here put into ur own words ltr

CFG to PDA (hw qn)

Sadly have to logic out mostly, here’s a quick example with a language generating $0^n{1}^n$ or $1^n{0}^n$

$$\begin{array}{c}{S}_1\to 0S_{1}1|ϵ\\ S_2\to 1S_{2}0|ϵ\\ \text{combining both:}\\ \boxed{S\to S_1|S_2}\end{array}$$

CFG to PDA

Consider the context-free grammar $G=(V,\Sigma ,R,S)$ with $V=\{S,T\},\Sigma =\{a,b,c\}$ and productions

$$\begin{array}{rl}S& \to aSc\mid T\\ T& \to bTc\mid \epsilon \end{array}$$

Description of $L(G)$:
Strings with some number of $a$‘s, followed by some number of $b$‘s, followed by $c$‘s, where the number of $c$‘s equals the total number of $a$‘s and $b$‘s.

Set notation:

$$L(G)=\{a^m{b}^n{c}^{m+n}\mid m,n\in \mathbb{N}\}$$

Explanation:
S defined as: “prepend some $a$ to the start and append some $c$, and add a S in the middle of them OR skip to T.
T is defined as: “prepend some $b$, append some $c$ put T in the middle, OR end the string.
$ϵ$ ends string

PDA Equivalence

• L(G) context free (CF)? → PDA recongizes it
• lang CF IFF PDA recongize it

Largest pt for midterm 2?

• mostly stuff aft midterm 1, but obv shuld know basic stuff (bool func / truth tables)

Show langauge is ! CFL

Example 23

In a way its a lot like how we did for the pumping lemma, having to staisy the premise of the PL for CFL, then move onto the $x^n$ case, then create several cases from there. You MUST cover every possible case, hence there will be multiple cases when proving (see as case 2, todo add case1).

Example 23

Again when starting, we consider some example eg.

$$\begin{array}{c}s=01^{p}01^p\end{array}$$

Then we generate a sample string from that and split it (sample string must be @ param by pump len p). We then satisfy pumping lemma (PL) for the CFL (context free languages). So we generate sample string s,:

$$s=01..1|01..1$$

Then because $|vxy|\le p$ where || = length, then (actually we cant move foward with this beacuse of below)