Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- playground:tin [19. 10. 2010, 07.34:24] – vytvořeno fiona
+++ playground:tin [30. 12. 2022, 13.43:01] (aktuální) – upraveno mimo DokuWiki 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
+**L = {//a<sup>i</sup>b<sup>j</sup>// | //j > i ≥ 1//}**
+Nechť //n// je libovolné.
+Volíme //w// = //a<sup>n</sup>b<sup>n+1</sup>// náležící //L//, platí |//w//| ≥ //n//.
+Pro každé //x//, //y//, //z// náležící Σ* existuje //w// = //xyz//, |//xy//| ≤ //n//, //y// ≠ //ε// platí:
+  * //x// = //a<sup>o</sup>//; //o// ≥ 0
+  * //y// = //a<sup>p</sup>//; //p// > 0
+  * //z// = //a<sup>n−o−p</sup>b<sup>n+1</sup>//
+Pro //i// = 5 platí: //xy<sup>i</sup>z// = xy<sup>5</sup>z = //a<sup>o</sup>a<sup>5p</sup>a<sup>n−o−p</sup>b<sup>n+1</sup>// = //a<sup>4p+n</sup>b<sup>n+1</sup>// ∉ //L// protože neplatí //n+1 > 4p+n ≥ 1//.
+Z pumping lemmy plyne, že //L// není regulární.

Kalábovi