Übung zur Vorlesung

Theoretische Informatik I

Prof. Christoph Kreitz / Jens Otten Universität Potsdam, Theoretische Informatik — Sommersemester 2004 Blatt 7 — Abgabetermin: 12. Juni 2004, 11.00 Uhr

Quiz 7

Markieren Sie die nachfolgenden Aussagen als ”wahr” oder ”falsch”.

[ ] Für jede rechtslineare Grammatik G mit einer Produktionsregel der Form A→uA gilt, dass L(G) nicht endlich ist.

[ ] Die Sprache L={a^{n}b^{n} | n∈IN} ist nicht regulär, kann aber durch eine lineare Grammatik beschrieben werden.

[ ] Für jede linkslineare Grammatik, die keine Produktionsregeln der Form A→ϵ enthält, gilt L(G)=∅.

[ ] Eine Sprache, die durch eine kontextsensitive Grammatik beschrieben wird, kann nicht regulär sein.

[ ] Jede Sprache, die durch einen ϵ-NEA erkannt wird, kann durch eine äquivalente rechtslineare Grammatik beschrieben werden.

Aufgabe 7.1 (Grammatiken, Umwandlung in/von NEAs)

Gegeben sei die Grammatik G=({S, T, U, V }, {a, b, c, d, e, f}, P, S) mit P ={S→ϵ, S→aS, S→Sb, S→T, T →dV, T →Ue, T →fU, U→ϵ, V →dT }.

1. Geben Sie den Typ dieser Grammatik an und eine Ableitung des Wortes addddebb.

2. Geben Sie einen regulären Ausdruck und einen NEA an, der die Sprache L(G) beschreibt.

3. Geben Sie eine rechtslineare Grammatik G=(V, T, P, S) an, die die Sprache L(G) beschreibt. Welchen Typ hat die Sprache L(G)?

Aufgabe 7.2 (Konstruktion von Grammatiken)

1. Konstruieren Sie eine rechtslineare Grammatik G=(V, T, P, S) für die Sprache L(R) mit dem regulären Ausdruck R=(0 + 1)^{∗}00(0 + 1)^{∗}.

2. Konstruieren Sie eine linkslineare Grammatik G=(V, T, P, S) für die Sprache L(R) mit dem regulären Ausdruck R=0^{∗}(1(0 + 1))^{∗}.

3. Konstruieren Sie eine Grammatik G=(V, T, P, S) für die Sprache L={ww | w∈{a, b}^{∗}}. Geben Sie den Typ Ihrer Grammatik an.

Übung zur Vorlesung Theoretische Informatik I Blatt 7

Aufgabe 7.3 (Grammatiken, Umwandlung in/von NEAs) [3 Punkte]

Gegeben sei die Grammatik G = ({S, T, U, V }, {a, b, c}, P, S) mit P = {S→T, S→aT, S→aT a, S→T a, T →ϵ, T →bT, T →cU, U→cV, V →cV, V →cT }.

1. Geben Sie den Typ dieser Grammatik an und eine Ableitung des Wortes abcccba.

2. Geben Sie einen regulären Ausdruck und einen NEA an, der die Sprache L(G) beschreibt.

3. Geben Sie eine rechtslineare Grammatik an, die die Sprache L(G) beschreibt. Welchen Typ hat die Sprache L(G)?

Aufgabe 7.4 (Konstruktion von Grammatiken) [3 Punkte]

1. Konstruieren Sie eine linkslineare Grammatik G=(V, T, P, S) für die Sprache L(R) mit dem regulären Ausdruck R=a^{∗}(b + cc^{∗}d)^{∗}e.

2. Geben Sie für ein beliebiges k∈IN (k≥1) eine Sprache L_{k} und eine rechtslineare Grammatik G_{k}=(V, T, P, S) mit |V |=k und L_{k}=L(G_{k}) an, so dass L_{k} von keiner rechtslinearen Grammatik G′=(V′, T′, P′, S′) mit |V′|<k beschrieben werden kann.

3. Konstruieren Sie eine Grammatik G = (V, T, P, S) mit |P |≤4 für die Sprache L={a^{n}b^{n}c^{n} | n∈IN und n≥1}. Geben Sie den Typ Ihrer Grammatik an.

Aufgabe 7.5 (Linkslineare Grammatiken und reguläre Sprachen) [3 Punkte]

Zeigen Sie, dass linkslineare Grammatiken genau die regulären Sprachen erzeugen können, d.h. jede linkslineare Grammatik erzeugt eine reguläre Sprache und jede reguläre Sprache kann durch eine linkslineare Grammatik erzeugt werden. Die folgenden beiden Richtungen müssen betrachtet werden.

1. Jeder NEA A=(Q, Σ, δ, q_{0}, F) kann in eine äquivalente linkslineare Grammatik G = (V, T, P, S) umgewandelt werden. Geben Sie ein allgemeines Verfahren zur Umwandlung eines NEA A in eine äquivalente Grammatik G an.

2. Jeder linkslineare Grammatik G=(V, T, P, S) kann in einen äquivalenten ϵ-NEA A=(Q, Σ, δ, q_{0}, F) umgewandelt werden. Geben Sie ein allgemeines Verfahren zur Umwandlung einer Grammatik G in einen äquivalenten ϵ-NEA A an.

Haben Sie Fragen, Anregungen oder Probleme? Lassen Sie es uns wissen!

• Prof. Christoph Kreitz, Raum 1.18, kreitz@cs.uni-potsdam.de, Tel. 0331/977 3060 Sprechstunde: immer, wenn die Türe des Raumes 1.18 offen steht, und am Mittwoch 11.00 bis 12.30 Uhr

• Jens Otten, Raum 1.20, jeotten@cs.uni-potsdam.de, Tel. 0331/977 3072 Sprechstunde: immer, wenn die Türe des Raumes 1.20 offen steht, und am Dienstag 14.00 bis 16.00 Uhr.