Beispielaufgaben Informatik – Theoretische Informatik Schritt 1 von 4 0% Aufgabe 1: Aussagenlogik Eine Aussage $\displaystyle{A}$ kann entweder wahr $\displaystyle{A}={1}$ oder falsch $\displaystyle{A}={0}$ sein. Aus der folgenden Tabelle ergeben sich die Werte für „nicht A“ ($\displaystyle\neg{A}$) und für die zusammengesetzten Aussagen „A und B“ $\displaystyle{A}\wedge{B}$ bzw. „A oder B“ $\displaystyle{A}\vee{B}$. $\displaystyle{A}\wedge{B}$ $\displaystyle{B}={0}$ $\displaystyle{B}={1}$ $\displaystyle{A}={0}$ 0 0 $\displaystyle{A}={1}$ 0 1 $\displaystyle{A}\vee{B}$ $\displaystyle{B}={0}$ $\displaystyle{B}={1}$ $\displaystyle{A}={0}$ 0 1 $\displaystyle{A}={1}$ 1 1 $\displaystyle{A}$ $\displaystyle\neg{A}$ 0 1 1 0 Welche Aussage trifft zu? $\displaystyle{A}\wedge{B}$ ist falsch, wenn A wahr und B wahr ist. $\displaystyle{A}\vee{B}$ ist wahr, wenn A wahr und B wahr ist. Die Aussage $\displaystyle{A}\wedge{\left({B}\vee{C}\right)}$ ist für die Belegung $\displaystyle{A}={1},{B}={1},{C}={0}$ wahr. falsch. Der Satz „Franz ist faul, aber nicht dumm“ setzt sich zusammen aus den Aussagen $\displaystyle{A}=$ „Franz ist faul“ und $\displaystyle{B}=$ „Franz ist dumm“. Welche Aussage entspricht diesem Satz? $\displaystyle{A}\wedge\neg{B}$ $\displaystyle{A}\vee\neg{B}$ Aufgabe 2: Endliche Automaten Das folgende Diagramm beschreibt die Regeln, nach denen gültige Benutzernamen gebildet werden. Ein Benutzername beginnt mit einem Großbuchstaben, gefolgt von mindestens einem Kleinbuchstaben. Es können beliebige Kleinbuchstaben folgen (Beispiele: Anna, Moritz). Die Regeln sollen erweitert werden, so dass zum Beispiel auch CarolineSchilling, JanPhilippRoth und JackMcGyver gültige Benutzernamen sind.Durch welchen zusätzlichen Übergangspfeil muss das Diagramm ergänzt werden, damit es die neue Anforderung erfüllt? Aufgabe 3: Prädikatenlogik Die Aussage „$\displaystyle\forall{n}{P}{\left({n}\right)}$“ bedeutet: für alle $\displaystyle{n}$ aus einer gegebenen Menge gilt die Aussage $\displaystyle{P}{\left({n}\right)}$. Ein Beispiel wäre die Menge der natürlichen Zahlen für $\displaystyle{n}$ und die Aussage $\displaystyle{n}\ge{0}$ für $\displaystyle{P}{\left({n}\right)}$, denn alle natürlichen Zahlen sind größer oder gleich Null. „$\displaystyle\exists{n}{P}{\left({n}\right)}$“ bedeutet: es gibt (mindestens) 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“. Diese Aussage ist wahr, wenn entweder beide Teilaussagen wahr oder beide falsch sind. Betrachten wir nun folgenden Ausdruck: $\displaystyle\exists{x}{\left({P}{\left({x}\right)}\wedge\forall{y}{\left({P}{\left({y}\right)}\Leftrightarrow{y}={x}\right)}\right)}$Welche Interpretation ist richtig? Es gibt kein $\displaystyle{x}$, so dass $\displaystyle{P}{\left({x}\right)}$. Es gibt genau ein $\displaystyle{x}$, so dass $\displaystyle{P}{\left({x}\right)}$. Es gibt 2 Lösungen für $\displaystyle{x}$, so dass $\displaystyle{P}{\left({x}\right)}$. Es gibt mehrere $\displaystyle{x}$, so dass $\displaystyle{P}{\left({x}\right)}$. Aufgabe 4: Grammatiken In der Informatik werden Sprachen oft mit Hilfe von Grammatiken ausgedrückt. Formal definiert besteht eine kontextfreie Grammatik $\displaystyle{G}={\left({N},{T},{S},{P}\right)}$ aus: $\displaystyle{N}$ endliche Menge der Nichtterminale, $\displaystyle{T}$ endliche Menge der Terminale, wobei gilt $\displaystyle{N}\cap{T}={\lbrace\rbrace}$ Startsymbol, $\displaystyle{S}\in{N}$ $\displaystyle{P}\subseteq{N}\times{\left({N}\cup{T}\right)}^{\ast}$ Regeln Ausgehend vom Startsymbol $\displaystyle{S}$ werden Nichtterminale mit Hilfe der Regeln aus $\displaystyle{P}$ ersetzt, bis nur noch Terminale vorhanden sind. Als Beispiel dient ein einfacher Satzbau bestehend aus Subjekt, Verb und Objekt, wobei die Nomen einen Artikel haben können. Gegeben ist die Grammatik: $\displaystyle{N}={\lbrace}$S, Subs, Verb, Obj, Art, Nom$\displaystyle{\rbrace}$ $\displaystyle{T}={\lbrace}$die, das, fliegen, lieben, obst$\displaystyle{\rbrace}$ und die folgenden Regeln $\displaystyle{P}$: S → Subs Verb S → Subs Verb Obj Subs → Nom Subs → Art Nom Obj → Nom Obj → Art Nom Art → die Art → das Nom → fliegen Nom → obst Verb → fliegen Verb → lieben Welcher der folgenden Sätze ist mit dieser Grammatik nicht möglich? fliegen lieben das fliegen obst fliegen fliegen fliegen fliegen lieben obst fliegen fliegen lieben fliegen
