1. Obstaja neka lema: L je regularen in L = L(M), kjer je M DKA z n stanji.
Če je L neprazen, potem L vsebuje neko besedo x, katere dolžina je <= n-1.
Torej, preveriti moramo vse besede do dolžine vključno n-1, da ugotovimo, če
je
jezik prazen.
2. Pri lemi 3.8...
3. Uporabimo tisti algoritem za odpravljanje nekoristnih simbolov,
in potem pogledamo, če je mogoče iz S izpeljati kako neprazno besedo...
Nekaj o tem je bilo že napisanega na telje listi, tako da malo
pobrskaj...
Lp
----- Original Message -----
From: "Blaz Grebensek" <[EMAIL PROTECTED]>
To: "FRIClist" <[email protected]>
Sent: Sunday, February 19, 2006 12:11 AM
Subject: Re: [Friclist] TOR1 ustni
Zivjo
ima kdo slucajno odgovore na ta vprasanja?
1. Kako dolge besede moramo preverjati, da ugotovimo če je nek jezik
prazen
2. dokaz o nepraznosti regularnega jezika
3. Kako ugotovim če je nek KNJ prazen?
bi lahko se napisali kje v knjigi za TOR 1 se nahaja odgovor?
je za 1. in 2. vprasanje odgovor v lemi 3.9?
thanks
LP Blaž
On 2/15/06, ... <[EMAIL PROTECTED]> wrote:
Hmm...sem sel pogledat v Vilfanovo knjigo in mi tole
glede skr. levih izpeljav ni cisto jasno. Mislim, da moras vedno
najprej narisati drevo izpeljav za doloceno besedo. Ce je
gramatika nedvoumna tako ali tako obstaja le eno. Nato se
pac sprehodis po drevesu tako, da pogledas najprej najbolj
leva poddrevesa...in sproti izpisujes vozlisca (simbole) drevesa,
ki jih obiskujes.
Glede dodatne snovi..se je potrebno nauciti prav vse v tistem .ps fajlu
na
njegovi strani?
Lp
Rok
----- Original Message -----
From: "Marko Kotar" <[EMAIL PROTECTED]>
To: "FRIClist" <[email protected]>
Sent: Wednesday, February 15, 2006 2:35 PM
Subject: Re: [Friclist] TOR1 ustni
> Ahm. Torej recimo se neka beseda izpelje na 2 nacina.
> Skrajno leva izpeljava je taka. Da vsebuje cim manj
> koncnih simbolov v skrajno levi spremenljivki in nato
> se v vseh naslednjih. Je to to?
>
> Kako gre pa pretvorba iz skladovnega avtomata v KNJ?
> nimam dobr napisan:
> delta(q,a,z)=(r,x1,x2,...,xn)
> <q,z,s> ---> a<r1,x1,r2><r2,x2,r3>...<r(n-1),xn,rn>
> Tole je neki cudno? se komu da popravt?
>
> --- "..." <[EMAIL PROTECTED]> wrote:
>
>> Skrajno levo izpeljavo...dobimo, ce v drevesu
>> izpeljav
>> vedno obiskujemo najbolj levo vozlisce pri
>> "sestavljanju"
>> neke izpeljave. Nekaj takega, no.
>>
>> Lp
>> Rok
>>
>> ----- Original Message -----
>> From: "Marko Kotar" <[EMAIL PROTECTED]>
>> To: "FRIClist" <[email protected]>
>> Sent: Wednesday, February 15, 2006 1:45 PM
>> Subject: Re: [Friclist] TOR1 ustni
>>
>>
>> > Ja problem je ko jezik vsebuje samo epsilon.
>> Takrat se
>> > ta epsilon obravnava po pretvorbi isto kot ga ne
>> bi
>> > blo. Torej je treba odstraniti samo nesmiselne
>> > produkcije. Torej take, ki se ne morejo nikoli
>> razviti
>> > v koncen simbole.
>> >
>> > Kaj je to skrajna levay izpeljava?
>> > Je to kej v zvezi z dvoumnimi gramatikami al kaj?
>> >
>> > LP
>> > Marko
>> > --- Mitar <[EMAIL PROTECTED]> wrote:
>> >
>> >> Zdravo!
>> >>
>> >> > Kaj pa tale odgovor: Gramatiko pretvorimo v NOC
>> >> ali NOG. Ce je
>> >> > produkcija glavnega simbola prazna (nima
>> >> produkcij), natanko tedaj je
>> >> > gramatika prazna. Se strinjate al ne?
>> >>
>> >> Le stopnja odstranjevanja nekoristnih produkcij
>> je
>> >> pri tema pretvorbama
>> >> pomembno. Ti se vedno lahko pretvoris v NOC in
>> NOG
>> >> ne da bi odstranjeval
>> >> nekoristne produkcije. In v tem primer to ni res.
>> >> Taksen odgovor je
>> >> torej po moje nenatancen in ne pove bistva.
>> Bistvo
>> >> je, da odstranis
>> >> nekoristne produkcije in da gramatika mora se
>> vedno
>> >> kaj producirati.
>> >>
>> >>
>> >> Mitar
>> >>
>> >>
>> >
>> >
>> > __________________________________________________
>> > Do You Yahoo!?
>> > Tired of spam? Yahoo! Mail has the best spam
>> protection around
>> > http://mail.yahoo.com
>> >
>>
>>
>
>
> __________________________________________________
> Do You Yahoo!?
> Tired of spam? Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com
>
