1
Ich bin eine kontextfreie Grammatik der Gestaltung dieser Sprache zu generieren:kontextfreien Grammatik und Reversal
{ w in {a,b}* | w is of the form uvu^R, where u and v are any strings in {a,b}* }
Ich würde definieren die ersten beiden Strings als:
U -> aU | bU | _
V -> aV | bV | _
Und dann diejenigen kombinieren :
S -> UV
Aber wie kann ich die Umkehrung als kontextfreie Grammatik ausdrücken?
Entschuldigen Sie meine kleinen Kenntnisse in diesem Thema noch. Während ich darüber las, stieß ich auf eine identische Lösung wie die, die Sie gepostet haben, aber ich verstehe sie nicht ganz. Würde "ababa" zum Beispiel so aufgeteilt werden, dass u = "ab" v = "a" und u^R = "ba" mit nur einer Grammatikzeile? – mjuopperi
@Gawwad: Die Syntax, die dieser Grammatik für "ababa" gegeben wird, wäre: "aUa" -> "a {bUb} a" -> "a {b {a} b} a" '. –
Als ich die Lösung gelesen habe, die Sie genauer gepostet haben, konnte ich das auch selbst erarbeiten. Ich habe den ganzen Tag mit endlichen Automaten und Regex gearbeitet, so wie diese Arbeit anfangs wirklich seltsam erschien. Danke für Ihre Hilfe! – mjuopperi