HW#3 --- last modified March 26 2020 03:48:00.

Solution set.

Due date: Mar 26

Files to be submitted:
  Hw3.zip

Purpose: To gain familiarity with context free languages and their applications. To gain more experience with pumping lemmas. To understand parsers for context free grammars. To understand normal forms for context free grammars.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 (Learning Outcome 1) -- Write a grammar for a language described otherwise.

LO7 -- Be able to use a pumping lemma to show that some languages are not regular and/or not context-free Use closure properties to simplify proofs of non-regularity of languages.

Description:

This homework consists of some exercises and a coding assignment. Put the written problems in a file Hw3.pdf, put your Java code in the file Cyk.java, and ZIP both into a file Hw3.zip. For the written part of the assignment do the following problems:

1. Give a context free grammar for the language `{ww^R | w \in {a,b,c}^{\star}}`. Implement this grammar in JFLAP. Show with screenshots and explanation the brute force parser for this grammar running on the string `a\b\c\c\b\a` with a derivation table.
2. Give with proof an example of a non-regular language accepted by an `s`-grammar.
3. Imagine we are trying to come up with a grammar for programming language blocks. Let `S` denote a statement, `B` denote a block, let `a` denote an assignment statement, let `i` denote an if statement, and let `e` denote an else. A first pass at a CFG for this might be:

   S -> B | ε| aS | IS
   I -> iS | iSeS
   B -> {S}
   

   Use the algorithm from class to convert the above CFG to Chomsky Normal Form.
4. 2NF is the variation of CNF where in we also allow rules A-> xy where `x` and `y` can be either a single variable or a single terminal. Show how to modify the CYK algorithm to work for grammars in 2NF.

For the coding part of the assignment I want you to code a program in the file Cyk.java which can parse a string over a {a,b} according to a CFG in 2NF. The grader will compile your Java program from a shell prompt using the line:

javac Cyk.java

Your program will then be tested on various inputs using lines in the format:

java Cyk grammar_file some_string

For example, the grader might type:

java Cyk my_grammar.txt aabba

If the grammar generates the string aabba, then your program should output YES and stop; otherwise, it should output NO and stop. It should also output NO and stop on invalid inputs. A grammar_file consists of a sequence of newline delimited lines of the form: Variable:Variable_Or_Terminal,Variable_Or_Terminal_Or_Empty. Here a variable is a string of 0's and 1's which serves as an identifier for that variable, and a terminal is either an 'a' or a 'b'. We use 'e' to denote empty string. Below is an example grammar file:

0:a,0
0:1,b
1:10,11
10:a,e
11:b,b
11:b,e

The string aabb is in the language generated from this grammar as: `{0} =>a{0} => a{1}b => a{10}{11}b => aa{11}b =>aa\b\b`. Here I am writing braces around the variables for clarity.