Lernkarten

Karten 80 Karten
Lernende 4 Lernende
Sprache Deutsch
Stufe Universität
Erstellt / Aktualisiert 29.03.2016 / 02.10.2018
Lizenzierung Keine Angabe
Weblink
Einbinden
0 Exakte Antworten 80 Text Antworten 0 Multiple Choice Antworten
Fenster schliessen

Auf welche drei gängigen Automatentopologien lässt sich die Worterzeugung herunterbrechen?

- Konkatenation, Verkettung von Zeichen (Sequenz)

- Selektion, Wahl eines Suffix (Fallunterscheidung)

- Wiederholung von Strings (Schleife)

Fenster schliessen

Welche Operatoren gibt es bei regulären Ausdrücken?

• = Verkettungsoperator

| = Selektionsoperator

\(\otimes\) = Wiederholungsoperator

\(\Lambda\) = Nulloperator

E = Einsoperator

[] = Klammern

Fenster schliessen

Wie sind reguläre Ausdrücke definiert?

Die Menge der regulären Ausdrücke \(REXP_\Sigma\) ist genau die Menge an Wörtern w, die über dem Alphabet \(\Sigma \cup \{\Lambda, E, \otimes, |, \circ, [, ] \}\) mit folgenden Regeln gebildet werden können:

1.) Der Nulloperator ist ein regulärer Ausdruck

2.) Der Einsoperator ist ein regulärer Ausdruck

3.) Alle Elemente des Alphabets sind reguläre Ausdrücke.

4.) Die Verknüpfungen regulärer Ausdrücke mittels der Operatoren sind ebenfalls reguläre Ausdrücke.

 

Hinweis: Selektionsoperator | wird als Vereinigung interpretiert.

Fenster schliessen

Was lässt sich über die Äquivalenz von endlichen Automaten und regulären Ausdrücken sagen?

Zu jedem endlichen Automaten A über \(\Sigma\) existiert ein regulärer Ausdruck \(a \in REXP_\Sigma\),sodass L(A) = L(a) gilt.

Fenster schliessen

Was sind Nonterminale und Terminale?

Nonterminale: Variablen, die in der Menge N zusammengefasst werden.

Terminale: nicht weiter ersetzbare Sprachbestandteile, die in der Menge \(\Sigma\) zusammengefasst werden.

Fenster schliessen

Was ist das Semi-Thue-System STS?

- Umformungs-/Wortersetzungs-/Stringersetzungssystem

- Regelsystem zur Transformation von Wörtern

- keine Unterscheidung zwischen Terminal- und Nonterminalsymbolen

- kein Startsymbol

Fenster schliessen

Wie funktioniert der Ableitungsprozess des Semi-Thue-Systems?

Ein Wort v lässt sich aus u erzeugen, falls eine Substitution \(x \to y\) existiert, wobei x Teil des Wortes u ist und y Teil des Wortes v.

Genutzt werden Produktionen aus P, die angeben, welche Substitutionen möglich sind.

Fenster schliessen

Wie ist das Thue-System definiert?

\(\forall (x,y) \in P \ \exists(y,x) \in P\), d.h. die Ableitung ist symmetrisch.