GRUDAT, ÖVNING 10

 Automater och textsökning

Det finns en knuthautomatuppgift på varje Tildatenta. Välj själv!
Nytt för i år är reguljära uttryck. Om uppfräschning behövs, kolla
www.mcb.mcgill.ca/~blanchem/250/Lecture37/Lecture37Handouts.pdf

Det är inte noga vilken variant av reguljära uttryck man använder.
Man kan skriva (a|b|c) eller [abc] eller (a+b+c).

  1 HAFSBADETS UPPBLÅSBARA BARBARA (Tildatenta 7 maj 2000 uppgift 3)

  2 HAFSBADETS TRAMPBÅTSSYNTAX (Tildatenta 7 maj 2000, uppgift 6)

  3 VÄRSTINGVRÅLSAUTOMAT (Tildatenta 31 aug 2000, uppgift 1)

  4 TJUGONDAGKNUTAUTOMAT (Tildatenta 16 jan 2001, uppgift 2)

  5 ORD AV TYPEN bbabbabbbaabbb
  * Skriv ett reguljärt uttryck för ord i alfabetet {ab} som
    innehåller ett jämnt antal a.
  * Rita en ändlig automat som känner igen sådana ord.
  * Skriv en syntax för sådana ord.
  * Skriv ett program som kollar att ord följer syntaxen.