IRZ Kolokvij 1 Flashcards
Zapiši definicijo stika L1L2
L1L2 = {xy | x € L1 and y € L2}
Zapiši strogo definicijo formalnega jezika L nad abecedo A
Je množica nizov simbolov abecede A
Zapisite strogi deniciji Kleenovega zaprtja L formalnega jezika L.
L* = (inf U i=0)Li
Dan je koncni avtomat K = (P;delta; sigma; p0; F), kjer so P mnozica stanj, delta vhodna abeceda, p0 zacetno stanje, F mnozica koncnih stanj in sigma funkcija prehodov.
a) Zapisite strogi definiciji funkcije sigma in L(K) za primer, ko je (a) K determinističen
in ko je (b) K nedeterministicen.
a)
sigma: P x delta –> P
L(K) = {x € delta* | sigma(p0, x) € F}
b)
sigma: P x delta –> 2^P
L(K) = {x € delta* | sigma(p0, x) (presek) F != 0 }
ali
L(K) = {x € delta* | sigma(p0, x) vsebuje stanje v F }
Katere formalne jezike sprejemajo (a) deterministicni koncni avtomati (b)
nedeterministicni koncni avtomati?
Sprejemajo regularne izraze
Kaj trdi lema o napihovanju za regularne jezike?
L regularen ⇒ (∃n)(∀z) [z ∈ L ∧ ∣z∣ ≥ n ⇒ (∃u, v, w)[z = uvw ∧ ∣uv∣ ≤ n ∧ ∣v∣ ≥ 1 ∧ (∀i ≥ 0)uv^iw ∈ L]]
kdaj sta avtoamta enakovredna
Če sprejmeta enak jezik
Zapiši definicijo prehodne funkcije e-NKA
sigma: P x (delta* U [e] ) –> 2^P
Naštej operacije, ki ohranjajo zaprtost regularnih jezikov
- unija
- presek
- kontantikacija
- Klenovo zaprtje
- komplement
- substitucija
- homomorfizem in inverzni homomorfizem
- kvocient
Dan je končni avtomat K = (P;delta; sigma; p0; F)
Razloži pomen simbolov
P - končna množica stanj
delta - vhodna abeceda s končno mnogo znaki
sigma - funkcija prehodov
p0 - začetno stanje, p0 ∈ P
F - množica končnih stanj, podmnožica množice P
Definiraj kvocient jezikov L1 in l2
L1/L2 = {x | Ey € L2 : xy € L1}
(L1/L2)L2 = L1napiši definicijo neprazne množice
M sprejme besedo dolžine l, kjer je l < n
n je število stanj
napiši definicijo neskončne množice
M sprejme besedo dolžine l, kjer je n ≤ l < 2n
n je število stanj
