Regularitet & Automater - #6


Forelæsning (17. maj)

Egenskaber ved kontekstfri sprog [Martin, kap. 4.3-4.5, 6.1-6.3]

Øvelser

[Martin]:

Ekstraopgaver:

Java:

Ugens finurlige opgave:

I denne opgave vil vi se hvordan regulære sprog kan bruges som abstraktioner af programmer skrevet i et simpelt programmeringssprog. Fra sådanne abstraktioner kan vi analysere visse aspekter af opførslen af programmerne.

Forslag til læsegruppe

Argumentér for at ethvert regulært sprog også er kontekstfrit. (Vi har set 2 forskellige beviser for dette!)

Beskriv lukkethedsegenskaber for klassen af kontekstfri sprog.

Repetér beviset for pumping-lemmaet (for kontekstfri sprog). Argumentér med udgangspunkt i tegningen af en "lang" streng, der deriveres af en CFG på CNF (slide 23).

Afleveringsopgave

Martin 6.2 (a) (s.220)

Husk at forklare grundigt hvordan du bruger pumping-lemmaet [Martin, Theorem 6.1].

Dette er sidste obligatoriske opgave. Aftal afleveringsfristen med din instruktor, så der bliver tid til feedback inden eksamen.


Sidst opdateret: 19. marts 2017, amoeller@cs.au.dk