Ask Your Question
0

Odstranenie lavej rekurzie

asked 2015-02-01 19:36:13 +0100

gandalf gravatar image

Ahojte, mohol by mi niekto poradit, ci som odstranil tu lavu rekurziu spravne?

S -> Sb | Ab
A -> Aa | BC
B -> ac | eps
C -> Cc | Aa | b

Najprv odstranim eps prechody a B dosadim do A

S -> Sb | Ab
A -> Aa | acC | C
C -> Cc | Aa | b

Teraz mam rekurziu v S, A, C

S -> AbS' | Ab
S' -> bS' | b
A  -> acCA' | acC | cA' |c
A' -> aA' | a
C  -> AaC' | Aa | bC' | b
C'  -> cC' | c

Je to takto spravne? Dakujem.

edit retag flag offensive close delete

1 Answer

Sort by » oldest newest most voted
1

answered 2015-02-01 20:50:18 +0100

Ondřej Máca gravatar image

updated 2015-02-03 18:08:43 +0100

v třetím rádku by měl být ty dvě c na konci velké. Tedy - CA' | C. Jinak je to asi dobře.

EDIT:
S -> AbS' | Ab
A -> acCA' | CA' C -> AaC' | bC'

S -> AbS' | Ab
A -> acAaC'A' | acbC'A' | AaC'A' | bC'A'

S -> AbS' | Ab
A-> acAaC'A' | acbC'A' | bC'A' | acAaC'A'X | acbC'A'X | bC'A'X
X -> aC'A'X | aC'A'

S' -> bS' | b
A' -> aA' | a
C' -> cC' | c

edit flag offensive delete publish link more

Comments

1

Diky, ano tam som sa pri prepise pomylil, inak vraj je este problemove to Cecko v A pravidle.

gandalf ( 2015-02-02 16:20:56 +0100 )edit

to je vlastne pravda. Jak jsi to teda vyresil? me napadlo akorat takovy slozity. Napsal jsem je do puvodni odpovedi, ale nevim jestli je to dobre a jestli to jde jednodusseji.

Ondřej Máca ( 2015-02-03 18:10:06 +0100 )edit

Proč je problémové to Cčko v A pravidle?

pechmich ( 2015-02-04 10:30:11 +0100 )edit
1

protože C se může přepsat na Aa. Takže z A jde vyderivovat na Aa - což je leva rekurze

Ondřej Máca ( 2015-02-04 10:58:40 +0100 )edit

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Stats

Asked: 2015-02-01 19:36:13 +0100

Seen: 569 times

Last updated: Feb 03 '15