Regularitet & Automater - #1

Forelæsning (5. april)

Regulære udtryk [Martin, kap. 1.4-1.6, 3.1] (Der forventes også kendskab til resten af kap. 1.)

Øvelser

Husk studiecafe! Her får du chancen for at arbejde med opgaverne og få hjælp af instruktorerne undervejs. (Brug også gerne Blackboard diskussionsforumet til spørgsmål og diskussioner.) Det forventes at man har læst ugens pensum og arbejdet med opgaverne inden de efterfølgende holdtimer.

[Martin]:

Andre opgaver:

(Bemærk: "andre opgaver" er ikke mindre vigtige end opgaverne fra [Martin]. De er udvalgt til at illustrere centrale pointer, som ikke er dækket af bogen.)

  1. (Vigtig!) Bevis lemma 2 fra slide 57 (svarende til lemmaet på side 6 i noten om induktion). Dette er en god øvelse i bevisteknikken "strukturel induktion"!

  2. Lad prefix være funktionen, der givet en streng xinsigma* returnerer mængden af præfikser af x. Det vil sige:

    prefix(x) = {yinsigma* | der findes et zinsigma* så x=yz}

    Eksempel: prefix(abc)={Lambda,a,ab,abc}.

    Bevis (eller argumenter uformelt for) følgende udsagn (som alle er relevante for afleveringsopgaven):
    1. for alle x,yinsigma*: prefix(xconcaty) = prefix(x) union {x}concatprefix(y)
    2. for alle Ssubsetsigma*:  unionxinS* prefix(x) = unioni=0,1,2,... unionxinSi prefix(x)
    3. for alle A,Bsubsetsigma*:  unionxinA unionyinB {x}concat{y} = unionxinA {x}concatunionyinB {y} = AconcatB

  3. Her er 23 praktiske opgaver i at lave regulære udtryk (stop når du synes du har forstået hvordan regulære udtryk og automater fungerer - de sidste 5 opgaver er ikke helt nemme... :-)

(Brug max 15 min. på de næste to opgaver. Hvis du allerede er overbevist om, at regulære udtryk er nyttige, så kan du godt springe disse opgave over.)

  1. Syntaksen for URL'er er formelt specificeret i RFC 1738, Uniform Resource Locators (URL) (se afsnit 5. BNF for specific URL schemes). Der anvendes en speciel notation:
    • alfabetsymboler står i "..." og specielle ASCII tegn skrives med hexcode %xx
    • | bruges i stedet for +
    • *X bruges i stedet for X*
    • 1*X betyder X*X
    • [X] betyder (X+Lambda)
    Hvis man f.eks. "optrævler" definitionen af httpurl, så ender man med et regulært udtryk for HTTP URL'er. Undersøg om følgende strenge er lovlige HTTP URL'er (dvs. matcher httpurl):
    1. http://130.225.16.54:80
    2. http://com
    3. http://x//%CA%FE%
  2. Syntaksen for email-adresser er formelt specificeret i RFC 2822, Internet Message Format (se afsnit 3.4 Address Specification). Hvis man f.eks. optrævler definitionen af addr-spec, så ender man med et (stort) regulært udtryk - forudsat at man (f.eks.) ikke tillader kommentarer inden i kommentarer (dvs. at en ccomment kan være en comment). Undersøg om følgende strenge er lovlige email-adresser (dvs. matcher addr-spec):
    1. a@b.c
    2. "@"@[1.2.3.4]
    3. #*!@!*#

Java:

Brug 5 minutter på at gøre dig bekendt med følgende resourcer:

Vi vil i de kommende uger opbygge en sådan RegAut pakke. Dokumentationen ovenfor kan bruges til at slå op hvad de enkelte klasser og metoder skal gøre, og forelæserens implementation kan bruges til afprøvning af funktionaliteten.

Forslag til læsegruppe

Følgende er forslag til eksamensforberedende aktivitet i læsegrupperne:

Repetér definitionerne af alfabet, streng, sprog, konkatenering (af strenge og sprog), Kleene stjerne, og syntaks og semantik af regulære udtryk, samt beviset for at klassen af regulære sprog er lukket under "Reverse".

Afleveringsopgave

Der vil i løbet af kurset blive stillet 6 små obligatoriske afleveringsopgaver. Afleveringsfrister aftales med instruktor. Aflevering skal ske via Blackboard, med mindre andet aftales med din instruktor. Det anbefales at man laver ugeopgaverne inden man begynder på afleveringsopgaven.

Første afleveringsopgave:

I opgave 2 ovenfor definerede vi funktionen prefix. Definer tilsvarende for et sprog S over sigma, at Prefix(S) er sproget bestående af præfikser af strenge fra S. Det vil sige:

Prefix(S) = unionxinS prefix(x)
  1. Lad r være det regulære udtryk a+bc. Hvad er de to sprog L(r) og Prefix(L(r))?
  2. Giv et konstruktivt bevis for at klassen af regulære sprog er lukket under Prefix, det vil sige: Hvis S er et regulært sprog, så er Prefix(S) også et regulært sprog.

    (Hint: givet et regulært udtryk r for S, vis ved induktion i strukturen af r, at der eksisterer et regulært udtryk r' hvor L(r')=Prefix(S).)

    Du må anvende følgende lemma (uden bevis): for alle i>0 og Ssubsetsigma*: Prefix(Si) = unionk=0...i-1 SkPrefix(S)

Besvarelser af afleveringsopgaverne er individuelle - du må gerne diskutere opgaverne med andre, men det er (af hensyn til din egen indlæring) ikke acceptabelt at kopiere løsninger. Idet afleveringsopgaverne er obligatoriske, er overtrædelser af disse regler at betragte som eksamenssnyd.

Sidst opdateret: 4. april 2017, amoeller@cs.au.dk