Kontextový „bezkontextový“ jazyk

[chimpsky]

Nedávno tu zaznělo, že bezkontextové jazyky s omezujícími podmínkami umí generovat i kontextové jazyky (a že parsing je NP-těžký). Byl by příklad?

[Reklama]

[zboj]

Nedávno tu zaznělo, že bezkontextové jazyky s omezujícími podmínkami umí generovat i kontextové jazyky (a že parsing je NP-těžký). Byl by příklad?

a^n b^n c^n, n>0

[Lolek]

Nedávno tu zaznělo, že bezkontextové jazyky s omezujícími podmínkami umí generovat i kontextové jazyky (a že parsing je NP-těžký). Byl by příklad?

a^n b^n c^n, n>0

To asi není kontextový ne? Mohl bys pls naznačit jak by vypadal zásobníkový automat, který jej příjme?

[Lolek]

Pardon, bezkontextový jsem myslel samozřejmě

[zboj]

Nedávno tu zaznělo, že bezkontextové jazyky s omezujícími podmínkami umí generovat i kontextové jazyky (a že parsing je NP-těžký). Byl by příklad?

a^n b^n c^n, n>0

To asi není kontextový ne? Mohl bys pls naznačit jak by vypadal zásobníkový automat, který jej příjme?

Přečti si otázku. Je to příklad kontextového jazyka přijímaného bezkontextovou gramatikou s omezujícími podmínkami.

[Reklama]

[Mirek Prýmek]

Přečti si otázku. Je to příklad kontextového jazyka přijímaného bezkontextovou gramatikou s omezujícími podmínkami.

Ten pojem "bezkontextová gramatika s omezujícími podmínkami" je nějaký terminus technicus, nebo to myslíme jenom neformálně? Existuje nějaká definice, co ta omezující podmínka může být, jaký může mít tvar? (Jako odpověď mi stačí jenom nějaké klíčové slovo, co se dá vygooglit. Vůbec si totiž neuvědomuju, že bysme se o "bezkontextové gramatice s omezujícími podmínkami" někdy učili)

[Mirek Prýmek]

To asi není kontextový ne? Mohl bys pls naznačit jak by vypadal zásobníkový automat, který jej příjme?

Pokud tomu rozumím správně, zboj myslel bezkontextový jazyk a^k,b^l,v^m, k>0, l>0, m>0 plus podmínka k=l=m, která z něj udělá kontextový.

[zboj]

To asi není kontextový ne? Mohl bys pls naznačit jak by vypadal zásobníkový automat, který jej příjme?

Pokud tomu rozumím správně, zboj myslel bezkontextový jazyk a^k,b^l,v^m, k>0, l>0, m>0 plus podmínka k=l=m, která z něj udělá kontextový.

Ano, tak nějak to vnitřně funguje. Tyto gramatiky se používají v NLP, ani ne kvůli té větší formální síle (přirozené jazyky jsou vesměs bezkontextové až na pár okrajových případů), ale protože se tak mnohem snáze vyjádří různá lingvistická pravidla (třeba jen shoda slovesa s podmětem apod.).

[zboj]

To asi není kontextový ne? Mohl bys pls naznačit jak by vypadal zásobníkový automat, který jej příjme?

Pokud tomu rozumím správně, zboj myslel bezkontextový jazyk a^k,b^l,v^m, k>0, l>0, m>0 plus podmínka k=l=m, která z něj udělá kontextový.

P.S. Pro zajímavost, jakákoliv gramatika s omezujícími podmínkami jde převést na ekvivalentní gramatiku jen s jedním pravidlem