Write a program that will eliminate inessential details from a Prolog program (for the purpose of plagiarism detection); your program should:
- Delete all spaces and tabs
- Only allow a single newline character after the end of a clause (i.e. after a full-stop), and nowhere else
- Rename all variables to "V" (a variable is a capital letter followed by any number of letters or digits)
- Rename all predicates to "p" (a predicate is a lower-case letter followed by any number of letters or digits)
- Remove all comments - a comment is anything between a "%" character and the end of that line.
Solution
Write a program that detects odd-length palindromes over the alphabet {a,b,c} where these palindromes contain exactly one c, always in the middle position. (Thus aabcbaa and ababcbaba are valid, whereas abab and cabac are not.) Your program should read a string, filter out everything except for a's, b's and c's and test to see if the resulting string is a palindrome of the above form. Your program should simply print out "yes" or "no". The following grammar for odd-length palindromes over the alphabet {a,b} may be of use:
```
	P -> a P a | b P b |  a | b
```
Solution
Assume that a string is any non-empty sequence of lower-case letters, and that "E" denotes the empty string. We define the following operations on strings:
- Concatenation, denoted by the operator "+", which joins two string together; thus abc + def is abcdef
- k-prefix, denoted by the operator ">", which gets (at most) the first k symbols of a string; thus 3 > abcd is abc
- k-suffix, denoted by the operator "<", which gets (at most) the last k symbols of a string; thus abcd < 3 is bcd
Write a program that takes in strings separated by these operators (and possibly using brackets), and evaluates the resulting string. Concatenation has highest precedence (i.e. gets done first), followed by k-prefix and then k-suffix; both concatenation and k-suffix are left-associative, whereas k-prefix is right associative. You can use the following grammar:
```
	StringExpr -> StringExpr + StringExpr
	StringExpr -> num > StringExpr
	StringExpr -> StringExpr < num
	StringExpr -> ( StringExpr )
	StringExpr -> string
```
Solution