die SprachenWas ist der Schnittpunkt zweier Sprachen?
L1={anb2m|n,m≥1}
L2={anb3n|n≥0}
L = L1 ∩ L2
Ich weiß Da L1 reguläre Sprache ist und L2 kann durch einen PDA dargestellt werden.
Aber ich verstehe nicht die Antwort, die besagt, dass L{a2nb6n|n≥1} ist. Wie wurde diese Lösung berechnet?
Eine Sprache ist nur ein Satz (von gültigen Strings), also ist das, was wir hier haben, wirklich nur ein einfaches Problem in der Ganzzahlarithmetik. Es ist nur notwendig, das elegante Kostüm der formalen Sprachen zu entfernen, um zum Kern des Problems zu gelangen.
Beide Sätze L1 und L2 sind Teilmengen von {acount(a)bcount(b)|j,k≥0}; das heißt, sie bestehen aus einer Anzahl von a s gefolgt von einer Anzahl von b s. Die Bedingung für L1 beschränkt count(b) auf eine positive gerade Zahl, da es für eine ganze Zahl m≥12m sein muss. Die Bedingung für L2 beschränkt count(b) auf genau 3×count(a).
Jetzt ist die Schnittmenge zweier mit Prädikaten definierter Mengen die Menge der Elemente, so dass beide Prädikate wahr sind. Also count(b) muss sowohl durch 2 als auch durch 3 teilbar sein, was bedeutet, dass es durch 6 teilbar sein muss; mit anderen Worten, es muss 6n für eine positive ganze Zahl n sein. Und das bedeutet, dass count(a) muss 2n sein, da es genau drei Mal so viele b s sind. Das gibt Ihnen die bereitgestellte Antwort.
Wie L2, L ist nicht regelmäßig, aber es kann mit einem sehr ähnlichen PDA implementiert werden.
Mögliche Duplikate von [Was ist der Schnittpunkt zweier Sprachen mit verschiedenen Alphabeten?] (Http://stackoverflow.com/questions/15213955/what-is-the-intersection-of-two-languages-with-different-) Alphabete) – veganaiZe
@rici das ist genau das, was ich nicht verstehe, 'L' ist im Grunde die Lösung – totoro
@totoro: OK, ich habe versucht, Ihre Frage zu bearbeiten, um klarer zu machen, was Ihr Punkt der Verwirrung war. Fragen wie diese sollten auf http://cs.stackexchange.com/ gestellt werden, da sie eigentlich nichts mit Programmierung zu tun haben. Beachten Sie jedoch, dass Ihre Frage dort nicht gut aufgenommen wird, wenn Sie nicht versuchen, Ihre Arbeit zu zeigen. – rici