Дефиниции К1 Flashcards
Регулярен израз
a. ∅ и всяка a ∈ Σ е регулярен израз;
b. Ако α и β са регулярни изрази, то α∘β, α∪β и α* са регулярни изрази.
Регулярен език за регулярен израз
Казваме, че един език L ⊆ Σ⋆ е регулярен, ако съществува регулярен израз r, такъв че
L = L(r)
(т.е. езикът, описван от регулярния израз r е точно L)
Краен недетерминиран автомат
Недетерминиран краен автомат е наредена петорка
N = ⟨Σ, Q, Qₛₜₐᵣₜ, Δ, F⟩, където:
Σ е крайна азбука (множество от символи),
Q е крайно множество от състояния,
Qₛₜₐᵣₜ ⊆ Q е множество от начални състояния,
Δ : Q × Σ → 𝒫(Q) е функция на преходите (връща множество от състояния),
F ⊆ Q е множество от финални състояния
Краен детерминиран автомат
Детерминиран краен автомат (ДКА) е наредена петорка
A = ⟨Σ, Q, qₛₜₐᵣₜ, δ, F⟩, където:
Σ е крайна азбука;
Q е крайно множество от състояния;
qₛₜₐᵣₜ ∈ Q е начално състояние;
δ : Q × Σ → Q е тотална функция на преходите;
F ⊆ Q е множество от финални състояния
Конфигурация за краен детерминиран автомат
Конфигурация е наредена двойка от вида (q, α),
където:
q ∈ Q – текущото състояние на автомата,
α ∈ Σ⋆ – частта от входната дума, която остава да се прочете
⊢ за краен недетерминиран автомат
Нека N = ⟨Σ, Q, Qₛₜₐᵣₜ, Δ, F⟩ е краен недетерминиран автомат.
Релацията ⊢ върху конфигурации се дефинира така:
(q, xα) ⊢ (p, α) ако p ∈ Δ(q, x)
⊢ за краен детерминиран автомат
Ако δ(q, b) = p, то
(q, bα) ⊢A (p, α)
т.е. автоматът в състояние q, четейки символа b от думата bα, преминава в състояние p и оставя за четене остатъка α
Кога една дума се разпознава от даден краен детерминиран автомат?
Дума α ∈ Σ⋆ се разпознава от детерминиран краен автомат A = ⟨Σ, Q, qₛₜₐᵣₜ, δ, F⟩, ако е изпълнено:
(qₛₜₐᵣₜ, α) ⊢⋆ (q, ε) за някакво q ∈ F
L(M) за краен детерминиран автомат
L(A) = { α ∈ Σ⋆ | δ⋆(qₛₜₐᵣₜ, α) ∈ F }
E(q) за краен недетерминиран автомат
E(q) = { p ∈ Q | (q, ε) ⊢⋆ (p, ε) }
Т.е. E(q) е множеството от всички състояния, достижими от q чрез поредица от ε-преходи (включително и самото q).
Релация на еквивалентност за даден език
Нека L е език над Σ⋆. Дефинираме релацията ≈L така:
α ≈L β ⇔ ∀ω ∈ Σ⋆ (αω ∈ L ⇔ βω ∈ L)
Език, разпознаван от автомат
L(A) = { α ∈ Σ⋆ | δ⋆(qₛₜₐᵣₜ, α) ∈ F }
Релация на еквивалентност между състояния (≡A)
p ≡A q ⇔ ∀ω ∈ Σ⋆ (δ⋆(p, ω) ∈ F ⇔ δ⋆(q, ω) ∈ F)
Обратен език (ляв и десен остатък)
L⁻¹M = { w | ∃u ∈ L, uw ∈ M }
ML⁻¹ = { w | ∃u ∈ L, wu ∈ M }
Дума и език над азбука
Дума над азбука Σ е крайна редица от символи от Σ.
Множеството от всички думи над Σ е Σ⋆.
Език над Σ е всяко подмножество на Σ⋆.
Конкатенация на езици
Нека A и B са езици. Тогава:
A · B деф = { α · β | α ∈ A и β ∈ B }
Звезда на Клини
За език A дефинираме:
A⁰ = {ε}
Aⁿ⁺¹ = Aⁿ · A
A⋆ деф = ⋃ₙ≥0 Aⁿ
Автомат на Майхил-Нероуд
Наричаме автомат на Майхил-Нероуд за език L:
M = (Σ, QM, qMstart, δM, FM)
където:
QM = {[α]L | α ∈ Σ⋆}
qMstart = [ε]L
δM([α]L, x) = [αx]L
FM = {[α]L | α ∈ L}
Автомат на Бжозовски
Нека L е език над Σ. Автоматът на Бжозовски за L е:
B = (Σ, QB, qBstart, δB, FB)
където:
- QB = { α⁻¹(L) | α ∈ Σ⋆ }
- qBstart = L = ε⁻¹(L)
- δB(M, x) = x⁻¹(M)
- FB = { M ∈ QB | ε ∈ M }
Т.е. всяко състояние M ∈ QB представлява производна на L по дума α.
Лема за покачването (регулярни езици)
Ако L е регулярен език, тогава:
∃p ≥ 1, такова че за всяка дума α ∈ L с |α| ≥ p съществуват x, y, z ∈ Σ⋆ такива че:
- α = xyz
- |y| ≥ 1
- |xy| ≤ p
- ∀i ∈ ℕ: xyⁱz ∈ L
Контрапозиция към рег. езици
Ако за всяко p ≥ 1, съществува дума α ∈ L с |α| ≥ p, такава че:
за всяко разбиване α = xyz, с |xy| ≤ p и |y| ≥ 1, съществува i ∈ ℕ с xyⁱz ∉ L,
то езикът L не е регулярен.
