# CSC 173: Computation and Formal Systems

## Fall 2010

Basic Course Information
Instructor: Professor Chris Brown
Workshop TA: Frank Ferraro
Grading TAs: Darcey Riley, Karl Lee, Thomas Thomas
Class Time: Tuesdays and Thursdays, 2:00pm-3:15pm, Gavet 301

Workshops: Mondays, 8:15pm in CSB 601

These workshops are completely optional. Their sole purpose is to help you better understand and master the material. One of the things that 173 helps to teach is that your peers can be of tremendous asset to you. To that end, these workshops are modeled after the official college-sponsored workshop program, so the main point behind them is to facilitate collaborative problem solving. However, these workshops are not affiliated with the college program, so the term "workshop" is somewhat of a misnomer. As a result, we are not restricted to the strict College workshop format; if the need arises, these sessions can easily become a Q&A session, or even more of a standard recitation. Regardless of the exact format, they will be motivated by you, and helped by the workshop TA.
Workshop Schedule
After every workshop, a brief outline of what was discussed will be posted. Generally, this will only be an outline (read: incomplete), intended to help those who cannot legitimately attend. If any interesting problems are discussed, the problems, hints, and/or solutions may be posted as well (most likely as PDFs).

11 October, 2010
Due to Fall Break, there was no workshop this week. The normal schedule resumes next Monday, October 18th.

4 October, 2010
• Predicates vs. functions
• In logic, there is a very big distinction: an n-ary predicate P takes n arguments and returns a truth value -- either TRUE or FALSE. An n-ary function f, on the other hand, takes n arguments and returns an m tuple of values in the domain. As an example, Female(Beth) is a predicate (and would most likely return TRUE) whereas mother(Beth) is generally (to logicians) considered a function and will return some individual (the mother of Beth).
• Prolog, however, tends to mix the two up. The same rule can function as either a predicate or as a function. For instance, consider the built-in rule append/3. You can use append(L1, L2, L3) as a function, where the return value is L3, which is the concatenation of lists L1 and L2; or as a predicate, where you ask if L3 can be unified as the concatenation of lists L1 and L2. For example, the call append([1,2], [a,b], L). (notice the period!) will return L = [1,2,a,b], while append([1,2],[a,b],[1,2,a,b]). will return Yes (true), but append([1,2],[a,b],[1,2,a]). will return No (false).
• Prolog is all about recursion, and understanding how to use it (i.e. winding and unwinding the stack) to your advantage!
• Prolog lists: naturally recursive
• Experimenting with exponentiation: please see this test file. Load with the call consult('test.prolog'). (again, don't forget the period!).
Try to understand the differences in the various exponentation rules (do some fail on some cases, but not necessarily on others? Do you understand the cut (!) operation?) Also, try to under my_append and how it works. Try the call ``trace, my_append([1,2],[a,b],L).'' (without quotes) for a better understanding.

27 September, 2010
Everything that was discussed was in review for the test, and a repeat of the 20 September workshop. Please see those notes if necessary.
• FIRST, FOLLOW and PREDICT sets
• Definition domains (FIRST on terminals and non-terminals; FOLLOW on non-terminals; PREDICT on production rules)
• Examples
• When is the empty string contained in any of these three sets?
• How to verify LL(1)-ness
• Foes to LL(1) grammars: left-recursion and common prefixes

20 September, 2010: Notes on topics discussed
• Why regular languages aren't sufficient
• (Partial) solution to problem: context-free languages
Theory:
• Context-free grammars
• (Non-deterministic) pushdown automata (PDA)
• Equivalence of CFLs, CFGs, and PDA
• Non-equivalence of deterministic PDAs (DPDA) and CFLs

(Slightly less) theory:
• Generation/parsing (acceptance)
• Ambiguous grammars
• Applications to compilers
• LL(1) and DPDAs can generally be sufficient for this task
• How to verify LL(1)-ness
• Foes to LL(1) grammars

13 September, 2010: Notes on topics discussed
• Regular languages, and ways to represent them
• Regular expressions
• DFAs
• NFAs
• NFAs with epsilon-transitions
• Connections between above representations
• Equivalence of above four
• Subset construction algorithm
• Building an NFA from a regex

6 September, 2010: Outline/discussion of topics covered
• Brief overview of C
• Pointers
• IO: File and STDIN
• Intro: How to debug using GDB
Seriously, learn to use GDB. You will need it later when you take other classes (e.g. 252). It can also make your life much easier. As an example: a friend and I were working on a C project once and (of course) had a segfault or two. We foolishly tried to debug it without using GDB or any professional debugging software, and it was a miserable time. We eventually realized how futile debugging that way was, and we took the time to learn GDB. In a very short time of using GDB we found our bug.
• Here is very handy sheet of GDB commands. It's very widely circulated online and I've lost the citation since finding it.
• Here is a very good intro/working example of GDB. We worked through it in the workshop.
• Here is the source code for the example I wrote. Try using GDB to find out where the bug is. This will also help you get a better understanding of C (hint!). Some additional notes:
• There are very few occasions when you should write code like that. I purposefully obfuscated it. In general, you want your code to be clear.
• I didn't comment it. Always comment your code. Always.
• Are you sure you've tested all the corner cases? What happens with malformed input?
• Brief overview of Linux
• Overview of C programming assignment, week 2

Last change: 27 Sept 2010