Forum:  Formale Sprachen & Automaten
Thema: Grammatik angeben für Dreierpotenz-Anzahlen von a
Themen-Übersicht
_LaVieJenniInfo
Junior
Dabei seit: 09.01.2021
Mitteilungen: 19
Themenstart: 2021-01-26 03:32

\(\{a^{3^{n+1}}| n \geq 0\}\)

Ich wollte eine kontextsensitive Grammatik dafür angeben, aber finde irgendwie durch ganz viel probieren keine, vielleicht kann mir jemand helfen.

Danke.


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2763
Beitrag No.1, eingetragen 2021-01-26 11:18

Die Wörter kann man schön als Folge der 3er-Potenzen darstellen.

Man kommt also von einem Wort zu nächsten, indem man alle Vorkommen eines Buchstaben verdreifacht.


Dazu braucht man:
- Einen Mechanismus zum Verdreifachen von Symbolen.
- Einen Mechanismus, der verhindert, dass man nur eine Teilmenge der Symbole verdreifacht.

Ansatz:
1. Erzeuge zunächst ein Wort der Form $T^{n+1}AX$.
2. Ein Mechanismus mit netto $TA\to AAAT$ verdreifacht die $A$s.
3. $AX\to A$, $TX \to X$ und $A \to a$ lösen schließlich auf.

Funktionsweise:
Um die $T$ zu entfernen, müssen diese komplett nach rechts wandern und dabei alle $A$ verdoppeln.

Für die ersten zwei Schritte müssen bei diesem Ansatz nun noch konkrete Grammatiken gefunden werden.
Das sollte aber nur eine Formalität sein.



_LaVieJenniInfo
Junior
Dabei seit: 09.01.2021
Mitteilungen: 19
Beitrag No.2, vom Themenstarter, eingetragen 2021-01-26 16:32

Ich bin gerade die ganze Zeit am überlegen, also meine jetzigen Gedanken:

S -> TAX

Wegen T^n+1

Habe ich mir überlegt noch eine Regel einzuführen: T -> TT

Aber werde dann irgendwie das T nicht los.


_LaVieJenniInfo
Junior
Dabei seit: 09.01.2021
Mitteilungen: 19
Beitrag No.3, vom Themenstarter, eingetragen 2021-01-26 16:54

Meine Regel macht keinen Sinn.

S -> TKAX
K -> TK

Meine das so ungefähr. oder?


DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 2763
Beitrag No.4, eingetragen 2021-01-26 17:32

Ich würde spontan vorschlagen:
$S \to KAX$
$K \to KK$
$K \to T$




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=251961=510001
Druckdatum: 2021-04-20 17:45