Assignment 1 - Formal Language Theory and Scheme Basics


This assignment is due at 11:00 pm, Friday February 3rd. Submission is by the submit command. Further submit instructions will follow.

According to the silent policy, no questions asked in any form after 11:00 pm, Thursday, February 2nd will be answered. Please ask any questions and ask for clarification early.

Clarifications

For the prefix grammar, each operation has exatly two arguments/operands. Make sure to define your "numbers".

Submission Instructions

Since things happen beyond your control, and since I do not want to penlize you too harsly for a slightly late assignment, this course has a somewhat generous late policy. Each student has three "late" days to be used as needed, across all four assignments. You may use one or two days on any assignment for any reason. Once you have used a late day, it is gone, so if you use all three days on your first assignment, no further late assignments will be accepted. Please use these days for genuine unforseen circumstances. An assignment from 5 minutes late to 24h late will use one late day. An assignment from 24h late to 48h late will use two late days. No assignment will be accepted more than two days late under any circomstances, as solutions will be posted two days after the deadline. Students with a documented reason (for example, a medical note) to be unable to submit two days late will have the marks from the assignment redistributed to the other assignments. Submit both of your files using the "submit" command, as assignment A1. Use the file names given, with the correct case, as your code will be automarked.

Part 1 - Formal Language Theory

Submit this part as a file named flt.txt

Part 1A - 12 Marks

For the following languages, state if they are regular, context free but not regular, or not context free. For each regular language, give a regular expression to generate this language. For each context free language, give a context-free grammar. For the languages that are not context-free, no proof is necessary.

A - All strings over the alphabet {a, b, c, d} with at least four instances of c and at least two instances of a

B - All strings over the alphabet {a, b, c, d} where there are more a's than d's

C - All strings over the alphabet {a, b, c, d} where no b is immediately followed by an a and no c is immediately followed by a d.

D - All binary (alphabet {0,1}) strings which represent integers in the Fibonacci series (integers encoded in the normal way, no leading zeros)

E - All binary strings which represent multiples of 3 (all strings are nonnegative integers encoded in the normal way).

F - All strings over the alphabet {a, b, c, d} where there are at least three times as many a’s as b’s

Part 1B Formal Languages continued - 6 marks

Recall the CFG shown in class for arithmetic. Make a similar CFG for arithmetic in prefix notation. Prefix, or Polish, notation may already be familiar to you from an earlier course, and should be familiar to you as you start to work with scheme. In an arithmetic expression in prefix notation, the operator comes before its operands.

We have the following binary operations:

Addition (+), Subtraction (-), Multiplication (*), Division (/).

We do not have unary negation in this system, and we consider negative integers to be integers.

We do not need parentheses () for grouping, except for unary negation. For example

1 + 1 is in infix notation.
+ 1 1 is the same thing in prefix notation

16 / ( -5 + 3) - 8 is in infix notation
- / 16 + -5 3 8 is its equivalent prefix form

(4 + 5) * 12 / 13 - 4 * -2 in infix becomes
- / * + 4 5 12 13 * 4 -2 in prefix

Write a context-free grammar for arithmetic on integers in prefix notation. Be sure to define your terminals.

Scheme Basics - 18 marks

Submit this part as a file named a1.ss

The first line of your file should be: #lang racket

Your code will be run on the mathlab system, using Doctor Racket.

Your task is to write a scheme program that takes, as input, a fully parenthesized infix arithmetic expression (with binary operators +, - *, and / ), and to turn it into a fully parenthesized prefix expression. Your function should be called infix_to_prefix and it should be called as follows:

(infix_to_prefix '((16 / ( -5 + 3)) - 8))

>(- (/ 16 (+ -5 3)) 8)

(Note - the quote needs to be there for execution, and initially the output expression was not fully parenthesized)

You may not use any of the imperative features of scheme, this includes all of the functions beginning with "!". Your solution should be properly tail recursive. You should create your solution as much as possible from the only the basic functions you've learned in class: first, rest, cons, and the predicates list? and eq?. You are expected to code in a functional style, and to make your code as readable as possible. Your code should be commented as necessary, and include a brief comment explaining your algorithm.