Streszczenie zagadnień z JAiO.pdf

1Wyznaczydjzykgenerowanyprzezpodanągramatyk

- reguły(teznaczkipoprawejodtrzałki)podpiadod1doiletamzaczynającodpierwzej

- zaczynamyodymbolupoczątkowegonpS

S -->

Ipodpiujemynadtrzałkązktórejreguł/regułykorzytamypoprotupodtawiając

Rekurencjajetkiedyymbolzlewejtronypowtarzaizprawejtronyiwtawiamytąreguł

priorytetowo(jakopierwzą)podpiującnadtrzałkąnumerregułyz*np 1* Przykładyrekurencjito

X-->XA , X-->AX

Po podstawieniu rekurencjiymboltojącyzprawejtronydajemydowymylonejpotgiWtym

przypadku XA^n lub A^n X

Zwykłeregułymożnawtawiadhurtemwpiującnadtrzałkąichnumerynp 1,2,3 izapiujeijew

wyrażeniuwnawiaiezeznakiem+któryoznaczawJO" albo ". Np. (<reg1> + <reg2> + <reg3>) .

WażneabyitrzymadpoziomuJakSmareguły1,2,3towhurcieniepodtawiamytezreguły4

którajetgdzieindziej

Gdynamwyjdziewyrażenie (y^k)*y lub y*(y^k) totrzebatokrócidwtenpoób y^(k+1) lub y^k

gdzie k=1,2,3....

ZWSZE(!)jakąjakiepotgitotrzebapodpiad n=0,1,2,3... ; k=1,2,3 itd.

- Zadaniejetdobrzezrobioneiniepochrzanilimykolejnocitowyjdąnakoocuamemałeliterki

2Przekztałciddanągramatyknagramatykbezregułzerowych

- regułyzerowetolambdyKażdąlambdtrzebaoddzielnieuuwadnieuuwającinnych

- regułybezużytecznetotakiedoktórychniemadojciaNpJetymbolXzlewejtronyanie

pojawiainigdziezprawejtoitokrela Przykażdymprzekztałceniuwartopopatrzedczynie

wytpują

*Podtawianiedziałanazaadzie

Podstawiamy A-->lambda

do B--> AB|AC

Towyjdzienamcotakiego B--> AB|AC|B|C

Bopierwzeiprzepiujeapotemiwtawia

Jakjużiwzytko"przemieli"tomamygotowezadanko

3Przekztałciddanągramatykdopotacimonotonicznej(prawdzidczyjetgramatyka

bezużyteczna)

- Takjakwzagadnieniunr2(pozbywanieilambdiwywalaniebezużytecznychreguł)

- Mająbydprzynajmniej2znakipoprawejtronie

- Można(anawettrzeba)podtawiadnp B-->1 ponieważtakjetłatwopozbydipojedynczych

znaków

4PrzekztałciddopotaciChomkiego

Chomsky - po prawej tronie2ymboleduże(np XX )lub1małyymbol(np y )

- bytakzrobidtrzebautworzydnoweregułynpmamytakiprzykład

S--> Xb|a

X--> cY|WW

robimy:

S-->Xb zatąp S-->XB ; B-->b

X-->cY zatąp X-->CY ; C-->c

i koniec zadanka:

S-->XB|a

X-->CY|WW

B-->b

C-->c

Ważneabyniepowieladregułnpgdy B-->b tonietworzydpotem D-->b .

5PrzekztałciddopotaciGreibach

- Pozbydirekurencjigdzierekurencjąjet-->AB, a nie A-->BA (rekurencja jest kiedy symbol stoi

na pierwszym miejscu)

- Zawsze prawdzadczyniemaregułzerowychczybezużytecznych

- RozwiązadtakabymałyymboltałwzdzienapoczątkuzprawejtronynpS-->aF|b|cDDD

Mamyprzykład S-->SB|AB|BC

Zaczynamy od Lematu 2 (pozbywanieirekurencji)

S-->SB

alfa - symbol(e) przy znaku rekurencji

beta - pozotałeregułyprodukcjiwreguleprodukcji

Czyliwtymprzykładzie

alfa = B

beta1 = AB

beta2 = BC

TworzymynowąregułprodukcjizwymylonymznakiemPojejprawejtroniemabyd

ala|ala_i_naz_nowy_wymylony_znak

kontynuującprzykładtworzymy

G-->B|BG

Terazwypieprzamynachamarekurencj SB zregułyprodukcji S . Ciach

DodajemyymbolGtamgdziewywalilimyrekurencj

Czyli z tego: S-->SB|AB|BC

Wychodzi to: S-->AB|BC|ABG|BCG

inakoniectychdziałaomamytak

G-->B|BG

S-->S-->AB|BC|ABG|BCG

I teraz:

Lemat 1 (podtawianieabybyłymałeymbolenapoczątku)

Podtawiamycoida,wywalamybezużyteczneikonieczadanka

6WyznaczydjzykbezkontektowybdącykonkatencjąumąlubdomkniciemKleeniego

- suma – dodadwzytkozL1iL2( L1+L2 )

- konkatencja – pomnożydkażdyzkażdym( L1*L2 )

- domknicieKleeniego – naprzykładzieL2leciizekładnikamidopotgod0doilutam

np. L2= {a,cb}

to L2*= {lambda, a, cb, aa, acb, cba, cbcb....

9PodadwzoryopiująceelementytablicyC-Y-K

- ponumerowaddobrzetablicC-Y-KzV(wpraworonądzieiątkiwdółjednoci)

- przepiadcałyzapi

Vadrezukanego={X|X→YZ

- napiadporednikuVxVwpotacinp

(„e”tonależydo) YeV11, ZeV24 } i podadtutajk=liczbajednotekprzypierwzymV

nprozwiązaniemdla V12 jest

V12={X|X-->YZ; YeV11, ZeV21} k=1

Przykładdla V15:

V15={X|X->YZ;YeV11, ZeV24} k=1

YeV12,ZeV33} k=2

YeV13, ZeV42} k=3

YeV14,ZeV51} k=4

WyznaczaitowzytkometodąVikoniec(ciachbachtoztym,toztymikonieczadania)

10WykorzytującalgorytmC-Y-Kprawdzidczypodanełowonależydogramatyki

- naryowadtabelC-Y-K

- w rogachuzupełnidznakamiłowapierwzegórnekratki

- obczaidwregułachcoprodukujądaneznaki

- wypełnicpierwzegórnekratkipokoleitymiregułami

- zrobidmetodąV

- nakoocu(tjV15)mawyjdymbolpoczątkowyJeżelinietołowonienależy

12Przekztałciddanągramatykregularnądopotaciwktórejymbolpoczątkowyniewytpuje

poprawejtronieregułprodukcji(thxtoSmuga)

tojettocomazprodukcje,ryujezwykre,poczymdorabiazkolejnywzełktóryprodukujeTO

SMOcopoczątkowyiwzytkiewzłyktórewkazywałynapoczątkowyprzerzucamynaniego?

typu:

S -> aA | bB

A -> aA | sS

B-> bB | sS

todorabiamywzełKizamieniamytak

K -> aA | bB

S -> aA | bB

A -> aA | sK

B-> bB | sK

13Przekztałcidpodanągramatykdopotaci deterministycznej

14Przekztałcidpodanągramatykdopotacizupełnej

Takjakwyżej(pkt13)plu

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: