Keresés

Keresendő kifejezés:

Toplista

Toplista
  • betöltés...

Segítség!

Ahhoz, hogy mások kérdéseit és válaszait megtekinthesd, nem kell beregisztrálnod, azonban saját kérdés kiírásához ez szükséges!

Pumpáló lemma?

54
Sziasztok!
Az det. és nemdet. automaták már nagyjából megy , viszont a pumpáló lemma feladatok teljes homály.
A fő dolog amit nem értek, az a particionálás része, hogy ha xyz részre particionáljuk akkor konrkétan mi az xy és z?

Itt egy konkrét feladat:
L = {0^i*1^j | i > j} nem reguláris
Tetszőleges p > 0 , kiválasztunk egy w szót pl w = 0^p+1 * 1^p eleme L. A |w| = 2p+1 >= p

Eddig világos

Felírjuk a lemma tulajdonságait:
Minden xyz eleme {0,1}*:
w = xyz
|xy| <= p
|y| > 0
Na és itt a w-ben ami most ugye 0^p+1 * 1^p mi konrétan xyz ??
Mert úgy folytatódik a feladat, hogy
|xy|1 = 0 (1-esek dbszáma xy-ban 0)
|y|1 = 0
De ezt a két dolgot honnan látjuk? 0^p+1 * 1^p -ban melyik x és melyik y ill. z ? Vagy hogyan kell ezt nézni?

A feladat vége pedig: i = 0 (ezzel kitöröljük y-t) -> |xz|0 <= |xz|1 = p
Jelenleg 1 felhasználó nézi ezt a kérdést.
pumpálólemma, pumpáló, lemma
0
Felsőoktatás / Matematika

Válaszok

1
Azért ezt a kérdést kiírhattad volna kicsit olvashatóbban is, mert tovább tart dekódolni, mint megválaszolni. Egyrészt a * operátor ebben a témakörben ismétlést jelent, te pedig (szerintem) konkatenációra használod. Másrészt a w=0^p+1*1^p elég értelmezhetetlen mint szó. Ha reguláris kifejezés lenne, akkor azt jelentené, hogy "`p` darab nulla VAGY legalább `p` darab egyes". De szerintem te azt akartad írni, hogy `w=0^{p+1}1^p`, tehát `p+1` darab nullát követ `p` darab egyes. De ez esetben a hatványozás magasabb precedenciájú, mint az összeadás, tehát zárójelezni kellett volna, szóval sehogy sem jó.

Na mindegy, én az `L={0^i 1^j | i gt j}` nyelvről fogom belátni, hogy nem reguláris, aztán majd javíts ki, ha mégsem ez volt a feladat. Indirekt módon bizonyítunk: feltesszük, hogy `L` reguláris, ekkor pedig teljesül rá a pumpálási lemma. A lemma azt mondja ki, hogy létezik olyan `p gt 0` szám, amelyre a nyelv minden legalább `p` hosszúságú `w` szava felírható `w=xyz` alakban úgy, hogy `y` nem üres szó, `|xy| le p`, és az `y` részszó `n`-szeri "pumpálásával" kapott `xy^nz` szó mindig eleme az `L` nyelvnek `n ge 0` választásától függetlenül.

Legyen a vizsgált szó `w=0^{p+1}1^p`. Az nyilvánvaló, hogy `w in L` és `|w| gt p`. A lemma szerint `|xy| le p`, és a mi szavunk `p+1` darab nullával kezdődik, tehát az `xy` részszó biztosan csupa nullából áll. Ebből triviálisan következik, hogy `y` is csupa nullából áll. (Ha jól értem, lényegében ez volt a kérdésed. De akkor már vigyük végig a bizonyítást.)

Most legyen `n=0` (a lemma szerint ez megengedett), tehát az `xy^0z=xz` szót vizsgáljuk. Ezt a `w` szóból úgy kapjuk, hogy kivesszük belőle `y`-t, amiről beláttuk, hogy csak nullákat tartalmaz. Viszont `w` csupán eggyel több 0-t tartalmazott, mint 1-et, ezért akárhány 0 szimbólumot is töröltünk ki, biztosan nem lesz már igaz, hogy több 0 van `xz`-ben, mint 1, tehát `xy^0z notin L`, vagyis a pumpálási lemma nem áll fenn, ellentmondásra jutottunk, a nyelv nem reguláris.
1