Bei­spiel­auf­ga­ben Theo­re­ti­sche Informatik

Auf­ga­be 1: Aussagenlogik

Eine Aus­sa­ge $\displaystyle{A}$ kann ent­we­der wahr $\displaystyle{A}={1}$ oder falsch $\displaystyle{A}={0}$ sein. Aus der fol­gen­den Tabel­le erge­ben sich die Wer­te für „nicht A“ ($\displaystyle\neg{A}$) und für die zusam­men­ge­setz­ten Aus­sa­gen „A und B“ $\displaystyle{A}\wedge{B}$ bzw. „A oder B“ $\displaystyle{A}\vee{B}$.

Auf­ga­be 2: End­li­che Automaten

Das fol­gen­de Dia­gramm beschreibt die Regeln, nach denen gül­ti­ge Benut­zer­na­men gebil­det werden.

Ein Benut­zer­na­me beginnt mit einem Groß­buch­sta­ben, gefolgt von min­des­tens einem Klein­buch­sta­ben. Es kön­nen belie­bi­ge Klein­buch­sta­ben fol­gen (Bei­spie­le: Anna, Moritz).

Die Regeln sol­len erwei­tert wer­den, so dass zum Bei­spiel auch Caro­li­ne­Schil­ling, Jan­Phil­ip­p­Roth und JackMc­Gy­ver gül­ti­ge Benut­zer­na­men sind.

Auf­ga­be 3: Prädikatenlogik

Die Aus­sa­ge „$\displaystyle\forall{n}{P}{\left({n}\right)}$“ bedeu­tet: für alle n aus einer gege­be­nen Men­ge gilt die Aus­sa­ge $\displaystyle{P}{\left({n}\right)}$. Ein Bei­spiel wäre die Men­ge der natür­li­chen Zah­len für $\displaystyle{n}$ und die Aus­sa­ge $\displaystyle{n}\ge{0}$ für $\displaystyle{P}{\left({n}\right)}$, denn alle natür­li­chen Zah­len sind grö­ßer oder gleich Null.

„$\displaystyle\exists{n}{P}{\left({n}\right)}$“ bedeu­tet: es gibt (min­des­tens) ein $\displaystyle{n}$, so dass $\displaystyle{P}{\left({n}\right)}$ gilt.

„$\displaystyle{F}\Leftrightarrow{G}$“ steht für „$\displaystyle{F}$ ist genau dann erfüllt, wenn $\displaystyle{G}$ erfüllt ist“. Die­se Aus­sa­ge ist wahr, wenn ent­we­der bei­de Teil­aus­sa­gen wahr oder bei­de falsch sind.

Betrach­ten wir nun fol­gen­den Aus­druck: $\displaystyle\exists{x}{\left({P}{\left({x}\right)}\wedge\forall{y}{\left({P}{\left({y}\right)}\Leftrightarrow{y}={x}\right)}\right)}$

Auf­ga­be 4: Grammatiken

In der Infor­ma­tik wer­den Spra­chen oft mit Hil­fe von Gram­ma­ti­ken aus­ge­drückt. For­mal defi­niert besteht eine kon­text­freie Gram­ma­tik \(\displaystyle{G}={\left({N},{T},{S},{P}\right)}\) aus:

1. N end­li­che Men­ge der Nichtterminale,

2. T end­li­che Men­ge der Ter­mi­na­le, wobei gilt \(\displaystyle{N}\cap{T}={\lbrace\rbrace}\)

3. Start­sym­bol, \(\displaystyle{S}\in{N}\)

4. \(\displaystyle{P}\subseteq{N}\times{\left({N}\cup{T}\right)}\cdot\) Regeln

Aus­ge­hend vom Start­sym­bol \(\displaystyle{S}\) wer­den Nicht­ter­mi­na­le mit Hil­fe der Regeln aus \(\displaystyle{P}\) ersetzt, bis nur noch Ter­mi­na­le vor­han­den sind. Als Bei­spiel dient ein ein­fa­cher Satz­bau bestehend aus Sub­jekt, Verb und Objekt, wobei die Nomen einen Arti­kel haben kön­nen. Gege­ben ist die Grammatik:

\(\displaystyle{N}={\lbrace}\)S, Subs, Verb, Obj, Art, Nom\(\displaystyle{\rbrace}\) \(\displaystyle{T}={\lbrace}\)die, das, flie­gen, lie­ben, obst\(\displaystyle{\rbrace}\) und die fol­gen­den Regeln \(\displaystyle{P}\):

S -> Subs Verb | Subs -> Nom | Obj -> Nom | Art -> die | Nom -> flie­gen | Verb -> fliegen

S -> Subs Verb Obj | Subs -> Art Nom | Obj -> Art Nom | Art -> das | Nom -> obst | Verb -> lieben