CIS301 Assignment 4

10 points. Due Saturday, March 8

We will use techniques from formal-language theory to build a "compiler" that translates a logical proposition into a format without conjunction operators and then "optimizes" (simplifies) the proposition by removing redundant operations and True/False constants.

The input to the translator is a line of text that contains a proposition written with letters, True, False, parentheses, and the operators AND(^), OR (v), and NOT (~). The proposition must be parenthesized, that is, p ^ (True ^ ~r) must be entered, rather than p ^ True ^ ~r.

First, all occurrences of ^ are replaced by ~ and v: 

A ^ B  ==>  ~(~A v ~B)
The rebuilt proposition has the same truth-table answer as the original. The example, p ^ (True ^ ~r), is translated to ~(~p v ~(~(~True v ~~r))).

Next, the expression is "optimized" by removing unneeded operators. Here are the steps that can be taken on the previous example: 

~(~p v ~(~(~True v ~~r)))
==>  ~(~p v (~True v ~~r))      (simplifying a double negation)   
==>  ~(~p v (False v ~~r))      (simplifying a  not)
==>  ~(~p v ~~r)                (simplifying an  or)
==>  ~(~p v r)                  (simplifying a double negation)
The rules used are 
 
~True ==>  False            ~False ==>  True
True v A ==>  True          A v True ==>  True
False v A ==>  A            A v False ==>  A
~~A ==>  A

Here is an example of a session with the translator: 

===================================================

> python run.py
Type proposition to translate: p ^ (True ^ ~r)

Parsed input: ['^', 'p', ['^', 'True', ['~', 'r']]]
which denotes (p ^ (True ^ ~r))

Translation:
ands removed:  ['~', ['v', ['~', 'p'], ['~', ['~', ['v', ['~', 'True'], ['~', ['~', 'r']]]]]]]
~(~p v ~~(~True v ~~r))
double negation removed: ['~', ['v', ['~', 'p'], ['v', ['~', 'True'], ['~', ['~', 'r']]]]]
]]
~(~p v (~True v ~~r))
negation removed: ['~', ['v', ['~', 'p'], ['v', 'False', ['~', ['~', 'r']]]]]
 ~(~p v (False v ~~r))
or removed: ['~', ['v', ['~', 'p'], ['~', ['~', 'r']]]]
~(~p v ~~r)
double negation removed:  ['~', ['v', ['~', 'p'], 'r']]
~(~p v r)

Output: 
['~', ['v', ['~', 'p'], 'r']]
which denotes ~(~p v r)

===================================================
The input syntax is defined by this grammar: 
EXPR ::=  ID  |  ( EXPR OP EXPR )  | ~ EXPR  |  True  |  False
OP ::=  ^  |  v
ID is a sequence of alphabetic letters (but not "v")
So, p is a legal input proposition, as are ~(p ^ q) and ~~((True v ~r) ^ (s v s)). Remember that parens are required with nested uses of ^ and v. (The outermost set of parens are optional.)

What you implement

I have written a parser that converts a proposition (string) into a nested-list parse tree. (In fact, the parser is generated from the grammar rules using the PLY (Python-Lex-Yac) domain-specific language.)

Your job is to write the functions that eliminate conjunctions (ANDs) and optimize the resulting tree. I have prepared an incomplete Python program, translate.py, and have indicated where you install the missing functions. There is a folder with the program and the needed parser and driver at the CIS301 assignments page.

The program is ready to be tested as is, and your job is to replace the dummy functions in it by real functions. Read the commentary embedded in the file before you add any of your own code.

This exercise will give you practice with grammars, dynamic data structures, and recursive function definitions. If you have never used Python before, please read the web page, Using Python for software development.

You can work solo or with a partner on this project. If you work with a partner, you are required to

  1. Tell the instructor (Schmidt) by the evening of Tuesday, March 4, who you are and who your partner will be for the assignment.
  2. Insert a comment at the top of your submitted program, stating your name and the name of your partner.
  3. Submit a copy of the completed program by the due date. (IMPORTANT: EACH PARTNER MUST SUBMIT A COPY TO KSTATE ONLINE.)

What to submit

I have included a file testcases.txt of test cases you must use to test your work. Do the tests in order, and you will have a smooth job.

For each test case, copy the output that the program generates into a txt file, tests.txt. Save the txt files with your completed program, translate.py, in a folder. Zip the folder and submit it to the CIS301 web page on K-State online.

You must submit both your completed program plus tests.txt to receive credit for working the assignment. Mr. Janovsky and I will copy your translate.py into our own folders that hold the parser and driver and run it. So, alter only translate.py.

(Finally, please do not try to check your program with the CIS301 proof checker, because the checker is unable to analyze programs that manipulate strings and lists of strings. Sorry! But do read the pre-post conditions and loop invariants in the code.)