Home, All Posts, RSS feed
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.
A CFG is a context-free grammar. A CFL is a context-free language. If you give me a CFL such as , then how can I make a grammar that generates it?
The first attack should always be to check if you can make by unioning together simpler languages. In this example, I don’t think we can’t break down at all, so we move on.
I usually guess a grammar 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
Since is in , it should be generated by . It is, but so is which is not in . We want to have separate states for our “adding ’s” time and our “adding ’s$ time, we don’t want to be able to go back and forth.
Here is a set of rules for that works:
And I think four states is the minimum.
Public Domain Dedication.