Definice: Nechť L je jazyk. L je regulární
jazyk (RJ), pokud existuje regulární výraz r, který tento jazyk značí.
Příklady:
r1 = ab + ba značí L1 = {ab, ba}
r2 = a+b* značí L2 = {anbm: n ³ 1, m ³ 0}
r3 = ab(a + b)* značí L3 = {x: ab je prefix x}
L1, L2, L3
, L4 jsou
regulární jazyky nad S
Konvence: L(r) označuje jazyk, který značí RV r.
Regulární jazyk (RJ)
Myšlenka: Každý RV značí regulární jazyk
r4 = (a + b)*ab(a + b)* značí L4 = {x: ab je podřetězec x}
5/29