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)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Gibt es eine linke Rekursion? (http://www.informatikerboard.de/board/thread.php?threadid=1802)

Geschrieben von jenny 53 am 29.01.2014 um 18:54:

  Gibt es eine linke Rekursion?

Wink
Ich habe noch eine Frage.
Ich habe eine kontextfreie Grammatik,die ich deterministich machen will..Ein Teil der kontextfreien Grammatik ist [latex] X \to XX|a [/latex].Gibt es bei dieser Regel eine linke Rekursion?Also muss ich diese Regel ersetzen mit den Regeln:
[latex] X \to aX' ,X' \to XX'|\varnothing[/latex] oder nicht?? verwirrt


Geschrieben von jenny 53 am 30.01.2014 um 15:51:

  RE: Gibt es eine linke Rekursion?

Zitat:
Original von jenny 53
Wink
Ich habe noch eine Frage.
Ich habe eine kontextfreie Grammatik,die ich deterministich machen will..Ein Teil der kontextfreien Grammatik ist [latex] X \to XX|a [/latex].Gibt es bei dieser Regel eine linke Rekursion?Also muss ich diese Regel ersetzen mit den Regeln:
[latex] X \to aX' ,X' \to XX'|\varnothing[/latex] oder nicht?? verwirrt


Wenn man die Regel [latex] Q \to QY|X [/latex] hätte,müsste man sie sicher ersetzen mit den Regeln
[latex] Q \to X|XQ',Q' \to YQ'| \varnothing [/latex]

Aber in diesen Fall,gibt es 2 mal ein [latex]X[/latex] ..Ist es also nicht der Fall??


Geschrieben von ed209 am 02.02.2014 um 11:38:

  RE: Gibt es eine linke Rekursion?

Zitat:
Original von jenny 53
Wink
Ich habe noch eine Frage.
Ich habe eine kontextfreie Grammatik,die ich deterministich machen will..Ein Teil der kontextfreien Grammatik ist [latex] X \to XX|a [/latex].Gibt es bei dieser Regel eine linke Rekursion?


Formale Sprachen ist bei mir schon ein bisschen her, aber
Laut hast du hier bereits die Definition von immediate left recursion erfüllt, sofern beta nicht mit A beginnt:

Zitat:

Immediate left recursion occurs in rules of the form

[latex]A \to A\alpha \mid \beta[/latex]

where [latex]\alpha [/latex] and [latex]\beta [/latex] are sequences of nonterminals and terminals, and [latex]\beta [/latex] doesn't start with [latex]A [/latex]. For example, the rule


Oder misverstehe ich jdeine Frage? verwirrt

Gruß,
ED


Geschrieben von jenny 53 am 02.02.2014 um 14:43:

  RE: Gibt es eine linke Rekursion?

Also gibt es eine linke Rekursion, die ich mit [latex] X \to aX' ,X' \to XX'|\varnothing[/latex] ersetzen kann,oder habe ich es nicht richtig verstanden? verwirrt


Forensoftware: Burning Board, entwickelt von WoltLab GmbH