Regularitet & Automater - #5

Forelæsning (10. maj)

Lukketheds- og afgørlighedsegenskaber ved regulære sprog [Martin, kap. 2.4]

• lukkethedsegenskaber (, , -, , , *, homomorfi og invers homomorfi)
• "pumping"-lemmaet
• beslutningsproblemer: membership, emptiness, finiteness, subset, equality
• Java: regaut.FA metoderne isEmpty, isFinite, subsetOf, equals og getAShortestExample

Kontekstfri grammatikker [Martin, kap. 4.1-4.2 (Theorem 4.9 dog først næste uge)]

• definition af CFG'er og deres sprog
• eksempler på kontekstfri grammatikker
• grammatik for Java (ikke pensum :-)

Øvelser

[Martin]:

• 2.22 (a+e) (s.81) - anvend pumping-lemmaet
• 2.27 (a+b+c+d+g) (s.82) - nye beslutningsproblemer
• 2.29 (a-h) (s.82) - konsekvenser af lukkethedsegenskaber
• 3.53 (s.127) - lukkethed under homomorfi og invers homomorfi (hint)
• 4.1 (a+b+e+f) (s.154) - læs og forstå CFG'er
• 4.10 (a+c+d) (s.156) - skriv CFG'er

Java:

• J11: Gennemlæs disse programstumper, overbevis dig om at de gør det ønskede, og udvid programpakken med dem:
  • FA.isFinite
  • FA.equals
• J12: Implementer flg. metoder (ialt. ca. 30 linjers programkode):
  • FA.isEmpty  (hint: brug findReachableStates)
  • FA.subsetOf  (hint: kombiner 2 eksisterende metoder)
  • FA.getAShortestExample
• J13: Vi kan nu lave et program, der sammensætter og grundigt afprøver de forskellige operationer.
  1. Som input tager programmet et alfabet (givet som mængden af tegn i en tekst-streng) og et regulært udtryk r (i form af en tekst-streng) over .
  2. Først oversættes r til en FA A.
  3. Derefter oversættes A til et regulært udtryk r' (som ikke nødvendigvis er identisk med r !).
  4. Til sidst oversættes r' til en minimal FA A' og der undersøges om sproget for A og A' er ens. (Hvis ikke, så er der en programmeringfejl et eller andet sted!)
  Prøv at køre programmet på et antal forskellige input. Denne test får grundigt afprøvet de fleste automatoperationer - men selv hvis denne test ikke afslører nogen programmeringsfejl er der selvfølgelig stadig en risiko for at de eksisterer.
• J14: Skriv følgende "gæt-et-regulært-udtryk" program (som ekstraopgaverne fra første uge):
  1. Programmet tager som input et alfabet (givet som mængden af tegn i en tekst-streng) og et regulært udtryk r (i form af en tekst-streng) over .
  2. Når programmet kører vil brugeren blive bedt om at indtaste et regulært udtryk r'.
  3. Programmet vil derefter undersøge om L(r)=L(r'). Hvis svaret er ja udskrives "ja!" og programmet stopper, hvis ikke, så udskrives et eksempel på en streng, der ligger i L(r) men ikke i L(r') (hvis en sådan eksisterer), og omvendt, en streng, der ligger i L(r') men ikke i L(r) (hvis en sådan eksisterer), og brugeren skal indtaste et nyt regulært udtryk.
  Ideen er at "mesteren" stiller "eleven" en opgave, f.eks. "skriv et regulært udtryk, der svarer til strenge med et ulige antal 1'er", starter programmet med et korrekt svar som input, og lader eleven afprøve sine gæt. (Hint: Brug RegExp.toNFA, NFA.removeLambdas, NFA.determinize, FA.minus, FA.isEmpty og FA.getAShortestExample.)
• J15: pumping-spillet
  Følgende programmer illustrerer det "kvantor-spil", der forekommer, når man prøver at bruge pumping-lemmaet til at vise, at et givet sprog er ikke-regulært:
  • Pumping1.class
  • Pumping2.class
  Hent class-filerne og prøv spillene med f.eks. "java -cp . Pumping1". Kan du vinde?

Ugens finurlige opgave:

Betragt igen delopgave 2 i den finurlige opgave fra 2. uge. Bevis at mængden af strenge, der repræsenterer korrekte multiplikationer, ikke er et regulært sprog.

Forslag til læsegruppe

Argumentér for at klassen af regulære sprog er lukket under følgende operationer: , , , , *. Involverer dine argumenter regulære udtryk eller automater? Prøv i hvert tilfælde at finde et alternativt argument, der bruger den anden formalisme.

Repetér beviset for pumping-lemmaet. Argumentér med udgangspunkt i tegningen af en "lang" streng, der køres på en FA (slide 11).

Beskriv algoritmer der løser basale beslutningsproblemer for regulære sprog: membership, emptiness, finiteness, subset, equality.

Repetér definitionen af CFG'er (Def. 4.6) og deres sprog (Def. 4.7).

Afleveringsopgave

Martin 2.22 (b) (s.81).

Husk at forklare grundigt hvordan du bruger pumping-lemmaet.