Wie können Lösungen einer diophantinischen Gleichung als Sprache ausgedrückt werden?

Mir wurde die Frage gestellt

Wo passt die folgende Sprache in die Chomsky-Hierarchie?

Nichtnegative Lösungen zur diophantinischen Gleichung . $(x,y)$ $3x-y=1$

Ich verstehe Sprachen wie , aber diese Sprache verwirrt mich. Wie sehen die Wörter in der Sprache aus? Wie könnte ich es mit einer Grammatik oder einem regulären Ausdruck darstellen? $L = \{ 0^n1^n \mid n \ge 1\}$

formal-languages computability justausr
quelle

Die Lösung für die Übung finden Sie unter Sprache des Diagramms einer affinen Funktion

Gilles 'SO - hör auf böse zu sein'

Antworten:

Das erste, was Sie tun möchten, ist, sich die Phrase selbst anzusehen und alle Verweise auf Sprachen für einen Moment zu ignorieren.

Was sind also die nicht negativen Lösungen für die Diophantin-Gleichung ? Wenn wir etwas fixieren , dann ist . Dies bedeutet, dass die Menge der Lösungen (beachten Sie, dass ein negatives und ein positives ein positives ergibt ). $3x-y=1$ $x$ $y = 3x-1$ $\{ (x, 3x-1)\ |\ x > 0 \}$ $x=0$ $y$ $x$ $y$

Jetzt können wir eine Zeichenfolge jedem nicht negativen Zahlenpaar : Zum Beispiel kann der Zeichenfolge zugeordnet werden . Wenn wir dies auf jedes Paar in der Menge anwenden, ist die resultierende Menge von Zeichenfolgen die Sprache dieser Menge. Beachten Sie, dass die Frage nicht wirklich klar macht, wie eine Zeichenfolge mit einer Lösung verknüpft werden kann, aber ich bin mir ziemlich sicher, dass sie die oben genannten Bedeutungen haben. $(x, y)$ $(100, 299)$ (100, 299)

Jetzt müssen Sie nur noch herausfinden, in welche Ebene der Chomsky-Hierarchie diese Sprache fällt. Da ich den leichten Verdacht habe, dass dies eine Hausaufgabenfrage ist, werde ich die Bohnen nicht sofort verschütten. Wenn Sie bestätigen können, dass dies keine Hausaufgabenfrage ist und Sie dennoch Hilfe benötigen, bearbeite ich die Antwort in.

Alex ten Brink
quelle

Es ist für Hausaufgaben. Ich weiß, dass das Generierungsproblem dafür nur mit einer Turingmaschine oder einem gleichwertigen Gerät lösbar ist. Ich kann sehen, wie das Erkennungsproblem auch sein würde, also wäre mein Gedanke, dass es die spezifischste Chomsky-Klasse ist, die rekursiv ist. Ich habe keine Ahnung, wie ich zeigen soll, dass es nicht kontextsensitiv ist.

Justausr

@justausr Die Sprache ist kontextsensitiv: Eine Sprache ist kontextsensitiv, wenn sie von einem Programm unter Verwendung von Nichtdeterminismus und höchstens linearem Raum analysiert werden kann (also nicht zeitgebunden). Ich bin mir ziemlich sicher, dass ich das analysieren 100, 100 * 3-1 berechnen und prüfen kann, ob es in linearer Zeit und damit in linearem Raum 299 entspricht, was diese Sprache kontextsensitiv macht.

Alex Ten Brink

meine Gedanken zu Hausaufgaben Fragen für das, was es wert ist, meta.cs.stackexchange.com/a/174/596

justausr

@AlextenBrink: Die Multiplikation dauert bei TMs quadratisch, der lineare Raum sollte jedoch funktionieren.

Raphael

@ Raphael Die Multiplikation zweier beliebiger unbegrenzter Ganzzahlen ist quadratisch, aber die Multiplikation einer beliebigen unbegrenzten Ganzzahl mit einer festen Konstante wäre linear, nicht wahr?

Ben

Die Problemstellung ist zwar unvollständig, aber wenn Sie dies sehen, können Sie davon ausgehen, dass " Ganzzahlen in Dezimalschreibweise darstellen " oder " Ganzzahlen in Binärschreibweise darstellen " gemeint war.

Also hier, wenn wir Binärformat annehmen, das Alphabet enthält 5 Zeichen: 0, 1, (, )und ,. Wenn wir eine Dezimalschreibweise annehmen, würde das Alphabet zusätzlich die Ziffern 2durch enthalten 9.

Die fragliche Sprache ist eine Teilmenge der Sprache, die mit dem regulären Ausdruck (in binärer Notation). . Wenn wir den einfacheren Fall der Gleichung annehmen würden, wäre die Sprache alle Zahlenpaare so dass . In binären bedeutet dies ist mit einem weiteren am Ende. Mit anderen Worten würde die Sprache aus Wörtern der Form . Wo passt das in die Chomsky-Hierarchie? $\mathtt{(}(0|1)^*\mathtt{,}(0|1)^*\mathtt{)}$ $2x-y=0$ $(x,y)$ $y = 2x$ $y$ $x$ 0( $x$ , $x$ 0)

Hier haben wir ein komplizierteres Beispiel: Sie müssen erkennen, ob . Wie vergleichen sich binäre (oder dezimale) Erweiterungen von und , wenn ? $y = 3x-1$ $x$ $y$ $y=3x-11$

Gilles 'SO - hör auf böse zu sein'
quelle

Die Frage ist nicht vollständig, da eine Sprache eine Reihe von Wörtern ist, keine Paare. Wenn Sie es als codieren, wobei binär sind, ist es kontextsensitiv, aber nicht kontextfrei (siehe Gilles 'Antwort). Wenn Sie es als codieren , ist es aber kontextfrei nicht regelmäßig (Übung), wenn Sie die Teile von und geeignet verteilen , ist es regelmäßig! Siehe hier . $x\$y$ $x,y$ $x\$y^R$ $x$ $y$

sdcvvc
quelle

Die Antwort ist noch trivialer, wenn die Codierung unär ist. Aber dann sollte diese Antwort hier sein , wo sie überflüssig wäre.

Raphael

Raphael: Ich bin anderer Meinung, diese Frage hat eine genau definierte Kodierung der Eingabe. Diese Frage tut es nicht und ich weise darauf hin, dass es wichtig ist.

SDCVVC

Ihre Kommentare zu den Klassen, in die die resultierende Sprache fallen würde, sind für diese Frage jedoch nicht hilfreich. Es geht nur darum, wie man solche Dinge überhaupt codiert.

Raphael