Toplista
- betöltés...
Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!
Pumpáló lemma?
Márk462
kérdése
687
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
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
pumpálólemma, pumpáló, lemma
0
Felsőoktatás / Matematika
Válaszok
1
AlBundy
{ Polihisztor }
megoldása
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.
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
- Még nem érkezett komment!