2.5. Balrekurzió megszüntetése

    1. közvetlen balrekurzió megszüntetése: A

      S → AA | Ba
      A → BAA' | aA'
      A' → BA' | λ
      B → SS | b
    2. balrekurzió megszüntetése: S

      S → AA | Ba
      A → BAA' | aA'
      A' → BA' | λ
      B → AAS | BaS | b
    3. közvetlen balrekurzió megszüntetése: B

      S → AA | Ba
      A → BAA' | aA'
      A' → BA' | λ
      B → AASB' | bB'
      B' → aSB' | λ
    4. balrekurzió megszüntetése: A

      S → BAA'A | aA'A | Ba
      A → BAA' | aA'
      A' → BA' | λ
      B → BAA'ASB' | aA'ASB' | bB'
      B' → aSB' | λ
    5. közvetlen balrekurzió megszüntetése:B

      S → BAA'A | aA'A | Ba
      A → BAA' | aA'
      A' → BA' | λ
      B → aA'ASB'B'' | bB'B''
      B' → aSB' | λ
      B'' → AA'ASB'B'' | λ
    1. közvetlen balrekurzió megszüntetése: C

      S → ABC
      A → BC | CB
      B → Ca | Ab
      C → AC' | aC'
      C' → CC' | λ
    2. balrekurzió megszüntetése: A

      S → BCBC | CBBC
      A → BC | CB
      B → Ca | BCb | CBb
      C → BCC' | CBC' | aC'
      C' → CC' | λ
    3. közvetlen balrekurzió megszüntetése: B

      S → BCBC | CBBC
      A → BC | CB
      B → CaB' | CBbB'
      B' → CbB' | λ
      C → BCC' | CBC' | aC'
      C' → CC' | λ
    4. közvetlen balrekurzió megszüntetése: C

      S → BCBC | CBBC
      A → BC | CB
      B → CaB' | CBbB'
      B' → CbB' | λ
      C → BCC'C'' | aC'C''
      C' → CC' | λ
      C'' → BC'C'' | λ
    5. balrekurzió megszüntetése: B

      S → CaB'CBC | CBbB'CBC | CBBC
      A → CaB'C | CBbB'C | CB
      B → CaB' | CBbB'
      B' → CbB' | λ
      C → CaB'CC'C'' | CBbB'CC'C'' | aC'C''
      C' → CC' | λ
      C'' → CaB'C'C'' | CBbB'C'C'' | λ
    6. közvetlen balrekurzió megszüntetése: C

      S → CaB'CBC | CBbB'CBC | CBBC
      A → CaB'C | CBbB'C | CB
      B → CaB' | CBbB'
      B' → CbB' | λ
      C → aC'C''C3
      C' → CC' | λ
      C'' → CaB'C'C'' | CBbB'C'C'' | λ
      C3 → aB'CC'C''C3 | BbB'CC'C''C3 | λ
    1. közvetlen balrekurzió megszüntetése: S

      S → aAS' | bBS'
      S' → SS' | λ
      A → Aa | b
      B → Bb | a
    2. közvetlen balrekurzió megszüntetése: A

      S → aAS' | bBS'
      S' → SS' | λ
      A → bA'
      A' → aA' | λ
      B → Bb | a
    3. közvetlen balrekurzió megszüntetése: B

      S → aAS' | bBS'
      S' → SS' | λ
      A → bA'
      A' → aA' | λ
      B → aB'
      B' → bB' | λ
    1. közvetlen balrekurzió megszüntetése: A

      S → BB
      A → SASA' | aA'
      A' → SAA' | λ
      B → b | Ba | Bb
    2. közvetlen balrekurzió megszüntetése: B

      S → BB
      A → SASA' | aA'
      A' → SAA' | λ
      B → bB'
      B' → aB' | bB' | λ
    1. balrekurzió megszüntetése: S

      S → ABC
      A → ABCa | Bb
      B → Aa | bb
    2. közvetlen balrekurzió megszüntetése: A

      S → ABC
      A → BbA'
      A' → BCaA' | λ
      B → Aa | bb
    3. balrekurzió megszüntetése: A

      S → BbA'BC
      A → BbA'
      A' → BCaA' | λ
      B → BbA'a | bb
    4. közvetlen balrekurzió megszüntetése: B

      S → BbA'BC
      A → BbA'
      A' → BCaA' | λ
      B → bbB'
      B' → bA'aB' | λ
    1. balrekurzió megszüntetése: S

      S → ABA | BAB
      A → ABAS | BABS | BB
      B → ABAS | BABS | bb | a
    2. közvetlen balrekurzió megszüntetése: A

      S → ABA | BAB
      A → BABSA' | BBA'
      A' → BASA' | λ
      B → ABAS | BABS | bb | a
    3. közvetlen balrekurzió megszüntetése: B

      S → ABA | BAB
      A → BABSA' | BBA'
      A' → BASA' | λ
      B → ABASB' | bbB' | aB'
      B' → ABSB' | λ
    4. balrekurzió megszüntetése: A

      S → BABSA'BA | BBA'BA | BAB
      A → BABSA' | BBA'
      A' → BASA' | λ
      B → BABSA'BASB' | BBA'BASB' | bbB' | aB'
      B' → BABSA'BSB' | BBA'BSB' | λ
    5. közvetlen balrekurzió megszüntetése: B

      S → BABSA'BA | BBA'BA | BAB
      A → BABSA' | BBA'
      A' → BASA' | λ
      B → bbB'B'' | aB'B''
      B' → BABSA'BSB' | BBA'BSB' | λ
      B'' → ABSA'BASB'B'' | BA'BASB'B'' | λ
    1. balrekurzió megszüntetése: S

      S → AaA
      A → BB | b
      B → CaC | aCa
      C → AaABS | cc
    2. balrekurzió megszüntetése: A

      S → BBaA | baA
      A → BB | b
      B → CaC | aCa
      C → BBaABS | baABS | cc
    3. balrekurzió megszüntetése: B

      S → CaCBaA | aCaBaA | baA
      A → CaCB | aCaB | b
      B → CaC | aCa
      C → CaCBaABS | aCaBaABS | baABS | cc
    4. közvetlen balrekurzió megszüntetése: C

      S → CaCBaA | aCaBaA | baA
      A → CaCB | aCaB | b
      B → CaC | aCa
      C → aCaBaABSC' | baABSC' | ccC'
      C' → aCBaABSC' | λ
    1. közvetlen balrekurzió megszüntetése: S

      S → CAS' | ACS'
      S' → SS' | λ
      A → BB | a
      B → Cb | bC
      C → a | BC | CB
    2. közvetlen balrekurzió megszüntetése: C

      S → CAS' | ACS'
      S' → SS' | λ
      A → BB | a
      B → Cb | bC
      C → aC' | BCC'
      C' → BC' | λ
    3. balrekurzió megszüntetése: B

      S → CAS' | ACS'
      S' → SS' | λ
      A → CbB | bCB | a
      B → Cb | bC
      C → aC' | CbCC' | bCCC'
      C' → CbC' | bCC' | λ
    4. közvetlen balrekurzió megszüntetése: C

      S → CAS' | ACS'
      S' → SS' | λ
      A → CbB | bCB | a
      B → Cb | bC
      C → aC'C'' | bCCC'C''
      C' → CbC' | bCC' | λ
      C'' → bCC'C'' | λ
    1. balrekurzió megszüntetése: A

      S → aSa | BSA | BSB
      A → a | B
      B → a | B | b
    2. közvetlen balrekurzió megszüntetése: B

      S → aSa | BSA | BSB
      A → a | B
      B → aB' | bB'
      B' → B' | λ

      Kicsit szokatlan az utolsó előtti szabály, melynek a bal és a jobb oldala megegyezik. Akár el is hagyható, mert nélküle is ugyanazt a nyelvet generálhatjuk a nyelvtannal.

    1. balrekurzió megszüntetése: S

      S → ABc
      A → a | Ba
      B → b | ABcb
    2. balrekurzió megszüntetése: A

      S → aBc | BaBc
      A → a | Ba
      B → b | aBcb | BaBcb
    3. közvetlen balrekurzió megszüntetése: B

      S → aBc | BaBc
      A → a | Ba
      B → bB' | aBcbB'
      B' → aBcbB' | λ