9. Context-Free Grammars

02/03/23

Chomsky type 3 = regular language - DFA, NFA, RE Chomsky type 2 = Content-free language(CFL) - Context-free grammars (CFGs), Push-down automata (PDA)

$2*(x+3)$ Expressions E Terms (part of +) T Factor (part of *) F

$\Sigma = \{a,*,+,(,)\}$ $E\to T$ $E\to E+T$ $T\to F$ $T \to T*F$ $F\to a$ $F\to (E)$

Can be shorthanded using or (|) statements

$E => T => I*F => F*F => a * F => a*(E) => a*(E+T) => a*(I+T) => a*(F+T) => a*(a+T) => a*(a+F) => a*(a+a)$

What is a CFG?

CFGs are a formalism to define languages that is more general than regular expressions; there are more languages definable by CFGs than by regular expressions and finite automata.

$G = (N,\Sigma,P,S)$ $N$ a finite state f non-terminal symbols $\Sigma$ (or $T$) a finite set of symbols (or terminal symbols) $N\cap \Sigma = \emptyset$

$P \subseteq_{fin} N \times (N \dot\cup \Sigma)*$ - finite set of productions $S:N$ the start symbol

$+\cup$ = not fresh

$=> \subseteq(N+\cup\Sigma)*\times(N+\cup\Sigma)*$

???

Language of a grammar

$L(G) = \{w:\Sigma*|S=>*w\}$

A CFL is a language given by CFG, $L=L(G)$

$L=\{a^nb^n|n:\mathbb{N}\}$

Theorem - Every REG is also a CFL REG $\subseteq$ CFL