Models of Computation | Lecture Notes 7

2016 September 30. Friday.

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.

Strategies to make a CFG from a CFL

A CFG is a context-free grammar. A CFL is a context-free language. If you give me a CFL such as $L = \{ a^n b^m a^k b^l : n + m = k+l \}$ , then how can I make a grammar $G$ that generates it?

The first attack should always be to check if you can make $L$ by unioning together simpler languages. In this example, I don’t think we can’t break down $L$ at all, so we move on.

I usually guess a grammar $G$ and then try some strings on it to see if I can generate them. If it works then I quit, if not then I see where I went wrong.

A first guess might be

$S \to aSa | aSb | bSa | bSb | \epsilon.$

Since $aaabbabbbb$ is in $L$ , it should be generated by $G$ . It is, but so is $abababab$ which is not in $L$ . We want to have separate states for our “adding $b$ ’s” time and our “adding $a$ ’s$ time, we don’t want to be able to go back and forth.

Here is a set of rules for $G$ that works:

$S \to aSB | T | U$

$T \to aTa | V$

$U \to bUb | V$

$V \to bVa | e$

And I think four states is the minimum.

Public Domain Dedication.