Ask Your Question
0

Odstranenie lavej rekurzie 2

asked 2015-02-02 16:27:56 +0100

anonymous user

Anonymous

Ahojte, nasiel som este jeden priklad, ktory mi nie je uplne jasne, ako sa dopracovat k vysledku. Zadana gramatika:

A → BC | a
B → CA | Ab
C → AB | CC | a

Toto je vysledok:

A → BC | a
B → CA | ab | CAB' | abB'
B' → Cb | CbB'
C → abCB | abB'CB | aB | a | abCBC' | abB'CBC' | aBC' | aC'
C' → ACBC' | AB'CBC' | CC' | ACB | AB'CB | C

Nie je mi jasne, preco som potom do Cecka dosadzoval Becko (predpokladam, ze preto lebo v Cecku bolo pravidlo BCB a tam vznika ta rekurzia), a potom som napr nedosadzoval do Acka Becko, kedze tiez tam je pravidlo BC. Viete mi niekto poradit? Pozeral som aj algoritmus v prednaskach, ale napriek tomu neviem na to prist. Dik.

edit retag flag offensive close delete

2 Answers

Sort by » oldest newest most voted
0

answered 2015-02-08 16:18:28 +0100

Hedgexu gravatar image

updated 2015-02-08 16:24:40 +0100

Dosazuješ tak aby si odhalil všechny levé rekurze. Já jsem se dostal k tomuto

({A,B,C,D,E},{a,b},P,A)

A -> BC | a
B -> ab |CA | abD |CAD
D -> Cb | CbD
C -> abCB | abDCB | ab | a | abCBE | abDCBE | abE | aE
E -> ACB | ADCB | C | ACBE |ADCBE | CE
edit flag offensive delete publish link more
0

answered 2015-02-07 11:06:47 +0100

Ondřej Máca gravatar image

updated 2015-02-07 11:07:17 +0100

Je ten v výsledek vážně dobře? Mě to vychází trošku jinak. (na dvou posledních řádcích jsem využil eps, abych tam nemusel psát spoustu věcí dvakrát)

C -> AB | a | ABC | aC  
C -> BCB | aB | BCBC | aBC | aC | a  
C -> CACB | abCB | CAB'CB | abB'CB | aB | CACBC | abCBC | CAB'CBC | abB'CBC | aBC | aC | a  
C -> abCBC' | abB'CBC' | aBC' | abCBCC' | abB'CBCC' | aBCC' | aCC' | aC'

C' -> ACBC' | AB'CBC' | CACBCC' | CAB'CBCC' | eps
edit flag offensive delete publish link more

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]

Question tools

Follow
1 follower

Stats

Asked: 2015-02-02 16:27:56 +0100

Seen: 771 times

Last updated: Feb 08 '15