Wir betrachten eine einfache Sprache als eine Menge von Zeichenfolgen. Mit EBNF können nicht nur Programmiersprachen sondern auch solche einfachen Sprachen beschrieben werden.

1. Geben Sie ein EBNF Beschreibung f¨ur folgende Sprachen an.
a) Die Sprache aller nat¨urlichen Zahlen in denen die Ziffer 9 genau einmal enthaltenist.

b) Die Sprache aller nat¨urlichen Zahlen die durch 5 teilbar sind.

c) Die Sprache aller nat¨urlichen Zahlen die durch 4 teilbar sind.

2. Es seien die boolschen Variablen A, B, C und die in der Vorlesung besprochenenOperatoren ^, _, ¬ sowie die Klammerung () gegeben.

Geben Sie die Syntax aller gültigen boolschen Ausdrücke mit den angegebenen Variablenund Operatoren in EBNF an.

Lösung:

1. a) <S> ::= ( “9″ {“1″|”2″|”3″|”4″|”5″|”6″|”7″|”8″|”0″} )
| ( (“1″|”2″|”3″|”4″|”5″|”6″|”7″|”8″){“1″|”2″|”3″|”4″|”5″|”6″|”7″|”8″|”0″}”9″ {“1″|”2″|”3″|”4″|”5″|”6″|”7″|”8″|”0″} )

b) <S> ::= “5″ | ( (“1″|”2″|”3″|”4″|”5″|”6″|”7″|”8″|”9″)
{“1″|”2″|”3″|”4″|”5″|”6″|”7″|”8″|”9″|”0″}(“0″|”5″) )

c) <S> ::= “4″ | “8″
| <V0> “0″ | <V0> “4″ | <V0> “8″ | <V1> “2″ | <V1> “6″<V0> ::= “2″ | “4″ | “6″ | “8″| <T> “0″ | <T> “2″ | <T> “4″ | <T> “6″ | <T> “8″<V1> ::= “1″ | “3″ | “5″ | “7″ | “9″| <T> “1″ | <T> “3″ | <T> “5″ | <T> “7″ | <T> “9″<T> ::= (“1″ | … | “9″) { “0″ | “1″ | … | “9″}

2. <S> ::= <Term>
<Term> ::= <Var> | (“¬” <Term>) | (<Term> <Op> <Term>) | (“(“<Term>”)”)<Var> ::= “A” | “B” | “C”<Op> ::= “_” |”^”