Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- deterministisch kontextfrei UND reguläre Sparache (http://www.informatikerboard.de/board/thread.php?threadid=1575)

Geschrieben von whatever am 06.08.2013 um 12:25:

  deterministisch kontextfrei UND reguläre Sparache

Meine Frage:
Hallo ich suche ein Beispiel für eine Sprache die deterministisch kontextfrei ist und gleichzeitig regulär.

Meine Ideen:
Es müsste theoretisch welche geben, aber leider habe ich keine gefunden... vielen Dank schon mal!


Geschrieben von Karlito am 06.08.2013 um 17:11:

 

Hallo,

das müsste doch einfach alle regulären Sprachen betreffen. Es gibt doch für jede reguläre Sprache einen deterministischen endlichen Automaten (DEA) welcher diese Sprache akzeptiert. Nun unterscheiden sich doch deterministische Kellerautomaten von DEAs nur darin, dass sie zusätzlich einen Keller benutzen können. Ich denke es sollte leicht sein, aus deinem DEA einen det. Kellerautomaten zu konstruieren, welcher die selbe Sprache akzeptiert.

VG,

Karlito


Geschrieben von whatever am 06.08.2013 um 18:00:

 

haha ich habe vergessen mit präfixeigentschaft dazuzuschreiben :-( sorry!


Geschrieben von Karlito am 06.08.2013 um 19:36:

 

D.h. kein Wort darf Präfix eines anderen Wortes sein.

Was hältst du von:

[latex]\mathcal{L} = \{0^n1 | n \in \mathbb{N} \}[/latex]

VG,

Karlito


Forensoftware: Burning Board, entwickelt von WoltLab GmbH