IB102 – úkol 10, příklad 2 Odevzdání: 14. 12. 2015
Vypracoval(a): UČO:
Skupina:
2. [2 body] Nechť Σ je libovolná abeceda a L, R ⊆ Σ∗
jsou libovolné jazyky nad touto
abecedou. O každém z následujících tvrzení rozhodněte, zda je pravdivé, a vaše tvrzení
dokažte:
a) L ≤m R a L není triviální =⇒ R není triviální
b) L ≤m R a R ≤m L =⇒ L = R
Připomeňme, že jazyk nad abecedou Σ je triviální, jestliže je roven ∅ nebo Σ∗
.