COMP712 Tutorial #4: Grammar and a bit of LISP – Answers
1: What is a grammar?
A set of rules that define a set of strings (sentences) over an alphabet (words) or simply, it is a set {S, Σ, N, P}
2: Give some examples of what kinds are specified in a grammar of a programming language?
Examples include where are things declared, what constitutes a statement in the language, what data types are allowed, etc.
3: Unlike natural language, the grammar of a PL is needed only to decide if an input string is a legal sentence or not. Why?
This is because we are not programming a computer to generate the programs by itself. Also, in a PL, one can only compute a legal sentence unlike NL.
4: What does Chomsky classification of language tell us about programming languages?
It tells us that you can restrict the rules in such a way that you could use different machines to decide if the input is a legal sentence for that language. Some languages (e.g. type 0) are too complex to handle and some (e.g. type 3) could be decided easily and efficiently.
5: Consider the grammar G:
S → aS
S → bA
A → ε
A → cA
Derive all the legal strings for this grammar.
{anbcm: n >= 0, m >= 0}
6: What is Kleene star? The symbol “*” used to denote 0 or more occurrences of a terminal on its left.
7: Consider the grammar G:
1. S aBC
2. S aSBC
3. aB ab
4. bB bb
5. CB BC
6. bC bc
7. cC cc
What are the terminals and non-terminals found in G?
Terminals are {a, b, c} and non-terminals are {S, B, C}. Note that non-terminals do not mean any term that appears on the left-hand side (lhs) of a rule but rather the one that appears on the left that gets expanded on the right. Hence a is not a non-terminal despite appearing on the lhs.
Provide one derivation for sentence aaabbbccc.
To work out the answer, look at what is required. You want a string, aaabbbccc. So if you start from S, it gives you either aBC or aSBC. If you choose rule 1, you will end up with S 1 aBC 3 abC which will not lead you to your required string. Hence you go back and try: S 2 aSBC.
Again, you can reduce S using either rule 1 or rule 2, giving:
S 2 aSBC 1 aaBCBC or S 2 aSBC 2 aaSBCBC
But the first option will introduce a “b” to the string:
S 2 aSBC 1 aaBCBC 3 aabCBC which is not you want.
So, you use: S 2 aSBC 2 aaSBCBC but which S-rule will you use, 1 or 2?
If you continue, your final answer should be:
S 2 aSBC 2 aaSBCBC 1 aaaBCBCBC 3 aaabCBCBC 5 aaabBCCBC 4 aaabbCCBC 5 aaabbCBCC 5 aaabbBCCC 4 aaabbbCCC 6 aaabbbcCC 7 aaabbbccC 7 aaabbbccc
What type is gammar G? – context sensitive
8: Construct a deterministic FSM that recognizes the set of all bit strings that contain the string 101.
The idea is you must be able to pick out 101 from a string like: 11100101000:
1
0
0
1
1
0
9: Given Σ = {0,1} , please provide the specifications for the following languages:
A. The language consists of all strings begin with 0 (e.g. {0} {00} {01}…)
S 0A*; A 0 | 1
B. The language consists of all strings begin with 0 and end with 1
S 0A*1; A 0 | 1
C. The language consists of all strings with odd lengths
S A [A A]*; A 0 | 1
10: The defining characteristic of grammar X is that the symbol to be re-written is to be re-written without reference to the context in which it occurs. What type of grammar is grammar X? Context-free or regular
11: In the lecture, we show that English is not a Type 3 grammar because it is a self-embedding language. Can you show, by example, that English is not a Type 2 grammar either? He likes apple vs *They likes apple [a * appearing in an English sentence is a way of saying this sentence is not grammatical]
One cannot write a CF-rule that expands the verb “like” without considering its context. The subject-predicate agreement in English means English cannot be a context-free grammar.
12. Write a function, add-item-to-list, that given an atom and a list of lists will add the atom to each list:
> (add-item-to-list 10 ‘((a b) (c d) (e f)))
((10 a b) (10 c d) (10 e f))
> (add-item-to-list 10 nil)
nil
(defun add-item-to-list (x L)
(cond ((null L) nil)
(t (cons (cons x (car L)) (add-item-to-list (cdr L))))))
13. Write a function, add-item-to-list2, that given an atom and a list will add the atom to all the lists in the list:
> (add-item-to-list2 10 ‘((a b) c d (e f)))
((10 a b) c d (10 e f))
> (add-item-to-list2 10 nil)
nil
(defun add-item-to-list2 (x L)
(cond ((null L) nil)
((listp (car L)) (cons (cons x (car L)) (add-item-to-list2 (cdr L))))
(t (cons (car L) (add-item-to-list2 (cdr L))))