Bezkontextový jazyk je formální jazyk , který je akceptovaný nějakým zásobníkovým automatem . Bezkontextové jazyky mohou být vygenerovány bezkontextovými gramatikami (viz Chomského hierarchie ).
Příklady
Typickým příkladem bezkontextového jazyka je
L
=
{
a
n
b
n
:
n
≥
1
}
{\displaystyle L=\{a^{n}b^{n}:n\geq 1\}
, jazyk všech slov sudé délky ve kterých první polovinu tvoří znaky
a
{\displaystyle a}
a druhou polovinu znaky
b
{\displaystyle b}
.
L
{\displaystyle L}
je generovaný gramatikou
S
→
a
S
b
|
a
b
{\displaystyle S\to aSb~|~ab}
a je akceptovaný zásobníkovým automatem
M
=
(
{
q
0
,
q
1
,
q
f
}
,
{
a
,
b
}
,
{
a
,
z
}
,
δ
,
q
0
,
z
,
{
q
f
}
)
{\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})}
kde
δ
{\displaystyle \delta }
je definována následovně:
δ
(
q
0
,
a
,
z
)
=
(
q
0
,
a
z
)
{\displaystyle \delta (q_{0},a,z)=(q_{0},az)}
δ
(
q
0
,
a
,
a
)
=
(
q
0
,
a
a
)
{\displaystyle \delta (q_{0},a,a)=(q_{0},aa)}
δ
(
q
0
,
b
,
a
)
=
(
q
1
,
ε
)
{\displaystyle \delta (q_{0},b,a)=(q_{1},\varepsilon )}
δ
(
q
1
,
b
,
a
)
=
(
q
1
,
ε
)
{\displaystyle \delta (q_{1},b,a)=(q_{1},\varepsilon )}
Bezkontextové jazyky jsou využívány především v programovacích jazycích . Například dobře uzávorkovaný výraz (tj. výraz, kde počet '(' je stejný jako počet ')') je generován gramatikou
S
→
S
S
|
(
S
)
|
λ
{\displaystyle S\to SS~|~(S)~|~\lambda }
nebo také
S
→
S
(
S
)
|
λ
{\displaystyle S\to S(S)~|~\lambda }
Uzávěrové vlastnosti
Bezkontextové jazyky jsou uzavřeny vzhledem ke zřetězení, sjednocení , iteraci, substituci, morfismu a rozdíl s regulárním jazykem , ale ne na průnik a rozdíl .
Související články
Pro bezkontextové jazyky existuje lemma o vkládání (pumping lemma) které udává nezbytnou podmínku, kterou musí jazyk splňovat, aby byl bezkontextový.
Normální formy
Každý bezkontextový jazyk lze převést do obou z následujících normálních forem (někdy také normálního tvaru):
Chomského normální forma
Gramatika je v chomského normální formě, pokud obsahuje pouze pravidla tvaru
X
→
Y
Z
|
a
{\displaystyle X\to YZ~|~a}
, kde
X
,
Y
,
Z
{\displaystyle X,Y,Z}
jsou neterminály a
a
{\displaystyle a}
je terminální symbol.
Greibachové normální forma
Gramatika je v greibachové normální formě, pokud obsahuje pouze pravidla tvaru
X
→
a
α
{\displaystyle X\to a\alpha }
, kde
α
{\displaystyle \alpha }
obsahuje libovolný (i nulový) počet neterminálů.
Teorie automatů : formální jazyky a formální gramatiky
gramatika
bez zvláštního názvu
indexovaná
stromová apod.
bez zvláštního názvu
—
jazyk
indexovaný
částečně kontextový
viditelný zásobník, vkládané slovo
bezhvězdičkový, neiterativní
nejjednodušší možný automat
rozhodovač, zaručeně skončí pro libovolný vstup
vnořený zásobník
vložený zásobník
viditelný zásobník, pro vkládané slovo
neperiodický konečný automat
Každá úroveň jazyků je podmnožinou své nadřazené úrovně. – Každý automat a každá gramatika má svůj ekvivalent v nadřazené úrovni.