Uebung04

Wie viele reguläre Ausdrücke gibt es?

Was kann man mit dem für reguläre Sprachen Pummping-Lemma zeigen?

• Man kann zeigen, dass eine Sprache kontextfrei ist.

• Man kann zeigen, dass eine Sprache nicht regulär ist.
• Man kann zeigen, dass eine Sprache regulär ist.
• Man kann zeigen, dass eine Sprache deterministisch ist.

Sei L eine reguläre Sprache. Dann gibt es eine natürliche Zahl n, so dass sich alle Wörter x aus L mit |x| >=n zerlegen lassen in x = uvw, so dass folgende Eigenschaften erfüllt sind:
- |v| >= 1

• - |uv| =< n

• - für alle i >= 0 gilt ____

Was sind die Eigenschaften einer Äquivalenzrelation

• Reflexivität, Symmetrie und Transitivität
• Siamkatze, Hauskatze, orangene Katze

• Reflexivität, Symmetrie, Intransitivität
• Reflexivität, Asymmetrie, Transitivität

Was besagt der Satz von Myhill-Nerode?

• Der Satz von Myhill-Nerode besagt, dass zwei Zustände in einem endlichen Automaten äquivalent sind, wenn sie die gleichen Zahlen akzeptieren bzw. ablehnen.
• Der Satz von Myhill-Nerode besagt, dass zwei Zustände in einem endlichen Automaten äquivalent sind, wenn sie die gleichen Wörter akzeptieren und ablehnen.
• Der Satz von Myhill-Nerode besagt, dass zwei Zustände in einem endlichen Automaten äquivalent sind, wenn sie die gleichen Buchstaben akzeptieren bzw. ablehnen.
• Der Satz von Myhill-Nerode besagt, dass zwei Zustände in einem endlichen Automaten äquivalent sind, wenn sie die gleichen Wörter akzeptieren bzw. ablehnen.