Assignment 2 for CSCI 431
Part 1: Parse trees
(This problem is taken from the notes posted for Aug 30th.) Given the following grammar for expressions:
E -> E + T | E * T | T T -> i | ( E )
Draw the parse tree for the expression:
2 * 3 + 4 * 5
Part 2: FSA's
Draw a Finite State Automata (FSA) for each of the following languages:
All even binary numbers
Binary numbers with the following form: 00(1|0)*11
All strings of a's and b's with an even number of b's
All strings of a's and b's with at most two consecutive b
Part 3: Regular Expressions using egrep
Read
this introduction to Egrep
and then write egrep-style regular expressions to search for:
lines that start with a period
lines that start with a period or comma
lines that start with a sequence of zero or more blanks followed by any number