Formaalit kielet ja automaattien teoria / syksy 2008

Harjoitus 3, viikko 39

1. Määritä relaation »_L määrittämät ekvivalenssiluokat kielelle

L = (aab È ab)*.

2. Olkoon G = (V, S, R, S) kielioppi, missä V = {a, b, S, A), S = {a, b} ja R koostuu produktioista

S ® AA, A ® AAA | a | bA | Ab

a) Mitkä kielen L(G) sanat voidaan johtaa korkeintaan kolmella askeleella?

b) Esitä vähintään neljä erilaista johtoa sanalle bbabbab.

c) Kuvaile sanan b^mabⁿab^p, missä m, n, p > 0, johtoa.

3. Konstruoi CF-kieliopit kielille

a) {a^mbⁿ | m £ n},

b) {w Î {a,b}* | w:ssä kirjaimen b esiintymien lukumäärä on sama kuin kirjaimen a esiintymien lukumäärä}.

4. Olkoon S = {a, b, (, ), È, *, f}. Konstruoi CF-kielioppi, joka generoi kaikki aakkoston S sanat, jotka ovat aakkoston {a, b} säännöllisiä ilmaisuja (Opastus: säännöllisten ilmaisujen määritelmä).

5. Olkoon G = (V, S, R, S) kielioppi, missä V = {a, b, S, A, B), S = {a, b} ja R koostuu produktioista

S ® aB | bA A ® a | aS | BAA B ® b | bS | ABB.

a) Esitä sanan ababba johto.

b) Osoita, että L(G) koostuu kaikista niistä aakkoston {a,b} ei-tyhjistä sanoista, joissa on yhtä monta a:n ja b:n esiintymää.

6. Anna kaksi luennoissa sivulla 35 olevan kieliopin mukaista sanan id*id+id johtoa, joista toinen johto on vasemmanpuoleinen ja toinen ei ole.