Računalništvo (FMF)/Vaje/1. kolokvij 2006-2007/Rešitev 1. naloge

Iz MaFiRaWiki

(a) Skonstruirajmo končni avtomat, ki razpoznava ta jezik (jezik je regularen natanko tedaj, ko obstaja končni avtomat, ki ga razpoznava)

Definirajmo peterko (Σ,Q,q0,F,d):

Σ={"a","b"}, Q={q0, q1, q2, q3}, F={q3}, začetno stanje je q0, prehodno funkcijo pa definiramo na sledeč način:

d[q0, "a"] = q2;
d[q0, "b"] = q1;
d[q1, "a"] = q1;
d[q1, "b"] = q1;
d[q2, "a"] = q2;
d[q2, "b"] = q3;
d[q3, "a"] = q1;
d[q3, "b"] = q3;

(b) Ne. Po lemi o napihovanju (Lema o napihovanju za regularne jezike) vemo, da jezik L = \{a^nb^n; n \in \mathbb{N}\} ni regularen.

Protiprimer:

L1:=\{a^n; n \in \mathbb{N}\}

L2:=\{a^nb^n; n \in \mathbb{N}\}

L_1 \cup L_2 je jezik {a*b*} - ta pa je regularen.

L1 in L_1 \cup L_2 sta regularna, L2 pa ni.

Glej tudi

Osebna orodja