Fall 2016, University of Kentucky, Models of Computation, CS 575, with Dr Judy Goldsmith. These incomplete lecture notes are just my own, not proofread or endorsed by Dr G or UKY.

Introducing context free grammars (CFG)

A CFG has four things:

A set of symbols . (nonterminals)

A set of terminal symbols which is disjoint from .

A set of rules where each rule maps some symbol in to some string made of symbols from

A chosen start symbol .

And we say “the language generated from a grammar ” is the set of terminal-only strings reachable from by following rules from the start symbol .

Example: make a grammar that generates a language

Let the language . In words, is the set of strings with more ’s than ’s.

Let’s make a grammar that generates this language.

Let our nonterminals be , let our terminals be , let our start state be . Here are our rules, we have two:

So to generate , we would start with , turn that into , then , then , then . A string is in the language generated by the grammar only if (first) you can follow rules from the start state and reach it and (second) only terminal symbols are in it.

Example 2: making a grammar that generates the palindromes

A palindrome is a string that reads the same backwards and forwards. Like racecar. Let’s make a grammar that generates all palindromes made from the alphabet .

Here is a set of rules that almost does it:

( means “nothing”, the empty string)

So to make we could go

But we can’t make or any other odd-length palindromes. To do that, we extend our rule:

And now generates all palindromes.

CFG’s are closed under concatenation

We say a language is context-free if there is some CFG that generates exactly it. We claim that if is context free and is context free, then the language $L_3 = {xy : x L_1, y L_2 } $ is also context free. ( is the set of strings that you can get by concatenating something from and something from .)

Why? Call ’s start state and ’s start state . Then we’ll make ’s start state and our grammar will only have one rule: