IB102 úkol 6, příklad 1 Odevzdání: 7. 11. 2016
Jméno: UČO: Skupina:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
1. [2 body] Nechť Σ = {∀, ∃,
.
=, 1} je abeceda a L je jazyk nad abecedou Σ definovaný předpisem
L = {u
.
=1m
| u ∈ {∀, ∃}∗
, m ∈ N0, #∀∃(u) + #∃∀(u) = m},
kde #v(u) značí počet výskytů řetězce v v řetězci u. Jinými slovy, jazyk L obsahuje všechny rovnosti
tvaru u
.
= 1m, kde počet alternací kvantifikátorů ve slově u ∈ {∀, ∃}∗ je roven m, tj. počet
kvantifikátorů ve slově u, po nichž následuje jiný kvantifikátor, je m.
Příklady slov patřících do jazyka L:
.
=, ∀
.
=, ∀∃
.
=1, ∀∀∃
.
=1, ∃∀∃
.
=11, ∃∀∀∀∃∃
.
=11
Příklady slov nenáležících do jazyka L:
ε, ∀∃
.
=, ∀∃
.
= 11, ∀∃
.
= ∀∃
.
=1
Sestrojte bezkontextovou gramatiku pro jazyk L. Stručně, neformálně zdůvodněte, proč vaše gramatika
generuje právě jazyk L.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.