IB102 – úkol 3, příklad 1 Odevzdání: 7. 10. 2013
Vypracoval(a): UČO:
Skupina:
1. [2 body] Uvažme abecedu Σ = {a, b} a uvažme jazyk L nad touto abecedou:
L = {xwx | x ∈ {a, b}, w ∈ {a, b}∗
}
Najděte nějakou pravou kongruenci ∼ s konečným indexem takovou, že jazyk L je sjednocením
některých tříd rozkladu Σ∗
podle ∼. Dokažte, že se jedná o pravou kongruenci,
včetně důkazu, že se jedná o ekvivalenci.
Rozhodněte, zda je jazyk regulární. Své rozhodnutí zdůvodněte.
1