06-11-2012, 05:27 PM
CSC173 Workshop: 20 Sept. Notes
1Workshop.pdf (Size: 152.96 KB / Downloads: 33)
C Programming, Weeks 3 and 4
The study of regular and context-free languages is preparing you for a rather large project
where you will write a command-line calculator program. I highly suggest you read the
guide provided by one of the TAs Karl Lee, available at http://www.csug.rochester.
edu/users/ugrads/jlee164/csc173/scanning_parsing_guide.pdf. Also, don't dawdle
and procrastinate on this project!
Context-Free Languages and Equivalent Forms
Recall that a language can be thought of a set L of strings w, where each w is some sequence
(possibly empty and possibly with repetition) of letters in an alphabet. Generally,
we donote that alphabet by the symbol .
Regular languages can be thought of as very simple pattern matchers, which can be very
eective as tokenizers, scanners, etc. However, they clearly have their limitations. For
example, it is impossible to construct a DFA that recognizes the language
Optional: A Formal Machine to Recognize CFLs
Recall that having regular expressions was okay, but the real applicatory power we got
from them was in the exploration of FAs: machines that could recognize the regular
expression. Similarly, we have some nice formalism with context-free grammars, but in
order to be of some use, it would be really nice if there were some way to recognize them.
For simplicity, we want this mechanism to be similar to FA, except we need to give it
some internal memory.