Informatiker Board | formale Sprachen | Gibt es eine linke Rekursion?

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Gibt es eine linke Rekursion?

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Gibt es eine linke Rekursion?

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

jenny 53
Mitglied

Dabei seit: 01.12.2013
Beiträge: 28

Gibt es eine linke Rekursion?

Zitatantwort auf diesen Beitrag erstellen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von jenny 53: 29.01.2014 19:02.

29.01.2014 18:54

Nehmen Sie jenny 53 in Ihre Freundesliste auf

jenny 53
Mitglied

Dabei seit: 01.12.2013
Beiträge: 28

RE: Gibt es eine linke Rekursion?

Zitat:

Original von jenny 53
Wink

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??

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von jenny 53: 30.01.2014 15:52.

30.01.2014 15:51

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

RE: Gibt es eine linke Rekursion?

Zitat:

Original von jenny 53
Wink

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

02.02.2014 11:38

Nehmen Sie ed209 in Ihre Freundesliste auf

jenny 53
Mitglied

Dabei seit: 01.12.2013
Beiträge: 28

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

02.02.2014 14:43

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Gibt es eine linke Rekursion?