Kääntäjät 11.4.2006

1. Annettu S = {1, 2, 3, 4} ja S:ssä määritelty relaatio R,
   R = { (4, 3), (2, 2), (2, 1), (1, 2), (3, 1) }
   Osoita, ettei R ole transitiivinen. Määrää relaatio R₁ ⊇ R siten, että R₁ on transitiivinen. Löydätkö toisen relaation R₂ ⊇ R, joka olisi myös transitiivinen?
2. Anna menetelmä, jolla voidaan määrätä annetun kieliopin aktiivit välisymbolit. Sovella seuraavaan kielioppiin:

   S → aBaC	B → bC
   S → daa	A → BaC
   B → dB	C → Ca
   	A → Ab

3. Määrittele seuraaville säännöllisille ilmauksille vastaavat äärelliset automaatit:
   1. l(l|d)*
   2. d*.dd*
   3. (a|b|c)xx*(a|b|c)
4. Millaiset kielet ovat LL(1)-kieliä? Anna esimerkki LL(1)-kielestä ja selvitä, miten LL(1)-kielten jäsentäminen tapahtuu rekursiivisen laskeutumisen menetelmällä.
5. Koodingenerointi?
   -Kerro erityisesti välikoodin käytöstä ja konekoodin muodostamisesta.