BEZKONTEXTOVÝ JAZYK

Základní
Rozšiřující

Typ formálního jazyka v ↗Chomského hierarchii gramatik a jazyků, nazývaný také jazykem typu 2. Je generovatelný formální ↗bezkontextovou gramatikou a rozpoznávatelný tzv. zásobníkovým automatem. Slova (řetězce znaků terminální abecedy) v b.j. se vyznačují tím, že mohou obsahovat jiná slova téhož jazyka: jde tu o tzv. ↗sebezapouštění (self‑embedding) podslov, které je potenciálně neomezené. Je to dáno tím, že při derivaci v bezkontextové gramatice se z neterminálního symbolu může vygenerovat týž neterminál obklopený z obou stran neprázdnými řetězci, schematicky X ==>* αXβ. Typickým příkladem b.j. je jazyk anbn, kde ab jsou symboly jeho vstupní abecedy, n je přirozené číslo ≥ 0. Takový jazyk není regulární, neboť jej nemůže vygenerovat žádná regulární gramatika, jelikož ta sebezapouštění není schopna. Velká většina struktur přirozených jazyků je bezkontextového n. regulárního typu (srov. ↗regulární jazyk), ovšem struktury s nespojitými/nesouvislými složkami, struktury typu a1a2an a b1, b2, … , bn (n ≥ 0), kde terminály ai a bi jsou spolu v syntaktickém vztahu, a struktury typu anbncn (n ≥ 0), kde figuruje vždy stejný počet tří (nejen dvou!) symbolů abc (příp. více), nejsou bezkontextové.

Citace
Vladimír Petkevič (2017): BEZKONTEXTOVÝ JAZYK. In: Petr Karlík, Marek Nekula, Jana Pleskalová (eds.), CzechEncy - Nový encyklopedický slovník češtiny.
URL: https://www.czechency.org/slovnik/BEZKONTEXTOVÝ JAZYK (poslední přístup: 19. 9. 2019)

CzechEncy – Nový encyklopedický slovník češtiny

Všechna práva vyhrazena © Masarykova univerzita, Brno 2012–2018

Provozuje Centrum zpracování přirozeného jazyka