CIS301 Programming Assignment 1

10 points. Due Friday October 9

We will use recursion techniques to build a translator that removes all occurrences of conjunction (AND) from a proposition.

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

The output is the proposition rebuilt so that all occurrences of ^ are removed and are replaced by ~ and v operators. The rebuilt proposition has the same truth-table as the original. The example, (p ^ (q ^ ~r)), is translated to ~(~p v (~q v r)).

There are two key steps in translating the input proposition:

  1. replacing all occurrences of (A ^ B) by ~(~A v ~B)
  2. replacing all occurrences of ~(~C) by C.
In the previous example, Step 1 produces ~(~p v ~~(~q v ~~r)), and Step 2 reduces this result to ~(~p v (~q v r)).

Here is an example of a session with the translator: 

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

> python Trans.py
Type proposition to translate: ( p ^ ( q ^ ~r ))
parsed input: ['^', 'p', ['^', 'q', ['~', 'r']]]
which denotes (p ^ (q ^ ~r))

ands removed:  ['~', ['v', ['~', 'p'], ['~', ['~', ['v', ['~', 'q'], ['~', ['~', 'r']]]]]]]
which denotes ~(~p v ~~(~q v ~~r))

double negations removed: ['~', ['v', ['~', 'p'], ['v', ['~', 'q'], 'r']]]
which denotes ~(~p v (~q v r))

===================================================
The printout shows the internal steps the translator takes:
(i) it splits the text into a list of the symbols/words inside it;
(ii) it builds the operator tree for the words;
(iii) it processes the tree, replacing subtrees of form, ["^", t1, t2], by ["~", ["v", ["~", t1], ["~", t2]]];
(iv) it processes the tree from (iii), replacing subtrees of form, ["~", ["~", t]], by t.

Here is another example: 

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

> python Trans.py
Type proposition to translate: (~s ^ (t v ~~u))
wordlist = ['(', '~', 's', '^', '(', 't', 'v', '~', '~', 'u', ')', ')']

parsed input: ['^', ['~', 's'], ['v', 't', ['~', ['~', 'u']]]]
which denotes (~s ^ (t v ~~u))

ands removed:  ['~', ['v', ['~', ['~', 's']], ['~', ['v', 't', ['~', ['~', 'u']]]]]]
which denotes ~(~~s v ~(t v ~~u))

double negations removed: ['~', ['v', 's', ['~', ['v', 't', 'u']]]]
which denotes ~(s v ~(t v u))

===================================================
The format of the input syntax is defined by this grammar rule: 
EXPR ::=  VAR  |  ( EXPR OP EXPR )  | ~ EXPR
          where  OP is  "^"  or  "v"
                 VAR is a sequence of one or more alphabetic letters
So, p is a legal input proposition, as are ~(P ^ Q) and (~~(pi v ~(r)) ^ (s v s)). Just remember that parens are required with every use of ^ and v.

What you must implement

I have done Steps (i) and (ii) for you; your job is to write two functions that do Steps (iii) and (iv). I have prepared an imcomplete Python program and have indicated where you install the missing functions. The program can be downloaded at http://www.cis.ksu.edu/~schmidt/301f09/Exercises/Projects/P1/Trans.py. The program is ready to be tested as is, and your job is to replace the two ``stub'' functions in it by real functions.

As implied by the previous paragraph, you must write the missing functions in Python. This 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) on Monday, 5 October, 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.)
As always, file copying and sharing are not allowed (except within each two-person team).

What to submit

Test your program on at least these test cases: 
p                       
         (should output  p  )
(p v q) 
         (should output (p v q)  )
(p ^ q)
         (should output  ~(~p v ~q)  )
~~~p
         (should output  ~p  )
( p ^ ( q ^ ~r ))
         (see above)
(~s ^ (t v ~~u))
         (see above)
(p v (q ^ (r ^ s)))
         (should output  (p v ~(~q v (~r v ~s)))  )
For each test case, copy the output that the program generates into a txt file. Save the txt files with your completed program, Trans.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 the output from the test cases to receive credit for working the assignment.

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!