Home, All Posts, RSS feed

Models of Computation | Lecture Notes 6

2016 September 21. Wednesday.

What is this?

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:

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

Example: make a grammar that generates a language

Let the language L = \{w \in (a+b)^\*: n\_a(w) > n\_b(w)\}. In words, L is the set of strings with more a’s than b’s.

Let’s make a grammar G that generates this language.

Let our nonterminals be N = \{S, T\}, let our terminals be T = \{a, b\}, let our start state be S. Here are our rules, we have two:

 S \to abS | aSb | Sab | baS | bSa | Sba | abST | aSTb | STab | baST | bSTa | STba | T

 T \to aT | a

So to generate baaba, we would start with S, turn that into bSa, then baSba, then baTba, then baaba. 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 \{a, b, c\}.

Here is a set of rules that almost does it:

 S \to aSa | bSb | cSc | \epsilon

(\epsilon means “nothing”, the empty string)

So to make abcb bcba we could go

 S \to aSa \to abSba \to abcScba \to abcbSbcba \to abcbbcba

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

 S \to aSa | bSb | cSc | \epsilon | a | b | c

And now G generates all a, b, c 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 L\_1 is context free and L\_2 is context free, then the language $L_3 = {xy : x L_1, y L_2 } $ is also context free. (L\_3 is the set of strings that you can get by concatenating something from L\_1 and something from L\_2.)

Why? Call L\_1’s start state S\_1 and L\_2’s start state S\_2. Then we’ll make L\_3’s start state S\_3 and our grammar will only have one rule:

 S_3 \to S_1 S_2

CFG’s are closed under union

Homework: Think about why.

Public Domain Dedication.