 L(3-nea) = L(nea) ?? |
chillerstu
unregistriert
 |
|
Meine Frage:
Guten Tag,
Guten Tag,
Ein 3-zustandsbeschränkter endlicher Automat (3-NEA) ist ein NEA, der genau 3 Zustände besitzt. Sei L(3-NEA) die Menge aller Sprachen, welche von einem 3-NEA akzeptiert werden.
Gilt L(3-NEA)= L(NEA) ?
Wie beweise ich die Gleichheit zweier Sprachklassen?
Meine Ideen:
Ich habe leider überhaupt keine Ahnung wie ich da rang gehen soll. 
|
|
22.06.2011 11:59 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
gleichheit wird durch gegenseitige Inklusion gezeigt. D.h. du zeigst, dass jedes Element der einen Sprache auch Element der anderen Sprache ist und umgekehrt.
Wie man das hier genau machen soll weis ich auch gerade nicht.
Aber vlt kannst du mit einem Gegenbeispiel argumentieren. Versuche einen 3-NEA anzugeben, der die Sprache mit dem Wort abcd akzeptiert. Weise nach, dass dies nicht mit 3 Zuständen machbar ist (ich glaube zumindest, dass dies nicht möglich ist.)
VG,
Karlito
|
|
|
23.06.2011 19:54 |
|
|
|
