**Lecture
11 (Variations on PDAs and CFGs), 2/22/17**

**Concepts, definitions (in italics):**

- Example: PDA
*M*for {_{2 }*ww*: w over {^{R}**a**,**b**}*} (p. 116) *Deterministic PDAs*can also be defined (p. 130)- Their
*expressiveness*is not the same as for "regular" PDAs, but between that of DFAs/NFAs and of PDAs *Deterministic CFL*-- accepted by some Deterministic PDA**0**^{n }1^{n}^{ }is deterministic*ww*^{R}is not^{ }

- PDAs that
*push strings* - A regular PDA is a special case of a string-pushing PDA
which happens to never push strings longer than 1 character
- Converting a PDA that pushes strings to one that pushes
single symbols onto the stack. (p. 119)
- String-pushing PDAs have
*same expressiveness*as regular PDAs (being able to push strings does not add power to PDAs) - Being able to push strings (rather than individual
symbols) does not add power to PDAs, though it adds convenience
- The 3 properties of
*simple*PDAs (p. 121) - Converting a regular PDA to a simple PDA.

o Involves three steps, that must be done in order (to avoid
undoing a condition)

*Simple*PDAs have same expressiveness as regular PDAs (these restrictions do not remove power from PDAs)*Chomsky Normal Form*: variation of a CFG, all rules of the form**A -> BC**or**A -> a**(p. 108)- CFGs in
*Chomsky Normal Form*are as powerful as regular CFGs - There is an algorithm for converting any CFG to an
equivalent one in Chomsky Normal Form
- 2 examples of restrictions on CFGs and how to convert
any CFG to an equivalent one with these restrictions
- Why do we create these variations on grammars or
machines? They are useful for constructing algorithms or for carrying out
proofs.
- Theorem: For any CFG, there exists an equivalent PDA
- Algorithm for converting a CFG
*G*to a*string-pushing*PDA*D* - 2 types of transitions in
*D*: *reduce*(read a character from input and pop same character from stack)*shift*(replace a variable on top of stack by its RHS in some rule of*G*).- These "shift-reduce" PDAs are
non-deterministic
- if there are multiple rules with same variable on left,
can use a shift transition for any one of these rules.
- Correspondence between shift transitions in the
*correct*computation of*D*and substitutions in the*leftmost*derivations of corresponding CFG - Shift-reduce parsers are a
*deterministic*algorithm used in compilers, which is based on simulating a shift-reduce PDAs. They use*lookahead*(peeking ahead in the input) to decide which rule to use when*shifting*

- Known as LL(k) parsers, where k is the size of lookahead (the other L stands for "leftmost",
see above)
- Deterministic languages always have a shift-reduce PDA
with
*finite*lookahead (sometimes 1, sometimes 2, etc)

**Reading:**

- Chapter 2.1 p. 108 to end (Chomsky Normal Form)
- Chapter 2.2 through middle of p. 121 (definition of
simple PDA)

**Skills:**

- Know new definitions, understand new concepts.
- Given a string-pushing PDA, create an equivalent
regular PDA.
- Given a regular PDA, create an equivalent simple PDA
- Given a CFG G, create an equivalent string-pushing PDA

**Notes:**

- When a string is pushed onto the stack, the leftmost
character appears on top.
- The grammar for which we constructed a PDA is the one
for simple expressions:

o S -> a S b | cc