| 1) |
Find a context-free grammar (BNF) for the following languages. [6 credits]
- All palindroms over the alphabet T = {a, b, c}. A palindrom is
a word that read backwards yields the same word; e.g. aa,
bbccbb, etc.
- All words over the alphabet T = {a, b, c} that
have at least two c characters; e.g. ccc,
abcbc, cacacac etc.
- All function calls to the functions f and
g. The function f has a
single argument, whereas function g can get
an arbitrary number of arguments, separated by commas.
Arguments are again function calls.
It is also possible to pass no parameter to g.
Here are examples for function calls: g(),
f(g()), g(g(), f(g())),
g(g(), g(), g()) etc.
|
| 2) |
Which of the languages of question 1 are regular? Prove
for the regular languages that they are indeed regular. [3 credits]
|
| 3) |
The following grammars define regular languages. Give a single EBNF
rule without recursion for every grammar. [6 credits]
-
A = a A | A b | c
-
A = A a b | A A | c
-
A = A a | B b B
B = B b | c
The word cbbca belongs to the language described
by the third grammar. Draw a derivation tree with respect
to the given BNF.
|
| 4) |
Find an EBNF grammar without recursion that specifies the syntax of
floating point numbers. The following numbers should be in the language
defined by your grammar: [3 credits]
-3.1415927, 1.4e10, 127.0e-2, -0.1e-1, .0
Integer numbers like 1, 4589 or -000335
(i.e. numbers without dots in the representation) should not be covered
by your grammar.
|
|
