\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\mathllap }[2][]{{#1#2}}\)
\(\newcommand {\mathrlap }[2][]{{#1#2}}\)
\(\newcommand {\mathclap }[2][]{{#1#2}}\)
\(\newcommand {\mathmbox }[1]{#1}\)
\(\newcommand {\clap }[1]{#1}\)
\(\newcommand {\LWRmathmakebox }[2][]{#2}\)
\(\newcommand {\mathmakebox }[1][]{\LWRmathmakebox }\)
\(\newcommand {\cramped }[2][]{{#1#2}}\)
\(\newcommand {\crampedllap }[2][]{{#1#2}}\)
\(\newcommand {\crampedrlap }[2][]{{#1#2}}\)
\(\newcommand {\crampedclap }[2][]{{#1#2}}\)
\(\newenvironment {crampedsubarray}[1]{}{}\)
\(\newcommand {\crampedsubstack }{}\)
\(\newcommand {\smashoperator }[2][]{#2\limits }\)
\(\newcommand {\adjustlimits }{}\)
\(\newcommand {\SwapAboveDisplaySkip }{}\)
\(\require {extpfeil}\)
\(\Newextarrow \xleftrightarrow {10,10}{0x2194}\)
\(\Newextarrow \xLeftarrow {10,10}{0x21d0}\)
\(\Newextarrow \xhookleftarrow {10,10}{0x21a9}\)
\(\Newextarrow \xmapsto {10,10}{0x21a6}\)
\(\Newextarrow \xRightarrow {10,10}{0x21d2}\)
\(\Newextarrow \xLeftrightarrow {10,10}{0x21d4}\)
\(\Newextarrow \xhookrightarrow {10,10}{0x21aa}\)
\(\Newextarrow \xrightharpoondown {10,10}{0x21c1}\)
\(\Newextarrow \xleftharpoondown {10,10}{0x21bd}\)
\(\Newextarrow \xrightleftharpoons {10,10}{0x21cc}\)
\(\Newextarrow \xrightharpoonup {10,10}{0x21c0}\)
\(\Newextarrow \xleftharpoonup {10,10}{0x21bc}\)
\(\Newextarrow \xleftrightharpoons {10,10}{0x21cb}\)
\(\newcommand {\LWRdounderbracket }[3]{\underset {#3}{\underline {#1}}}\)
\(\newcommand {\LWRunderbracket }[2][]{\LWRdounderbracket {#2}}\)
\(\newcommand {\underbracket }[1][]{\LWRunderbracket }\)
\(\newcommand {\LWRdooverbracket }[3]{\overset {#3}{\overline {#1}}}\)
\(\newcommand {\LWRoverbracket }[2][]{\LWRdooverbracket {#2}}\)
\(\newcommand {\overbracket }[1][]{\LWRoverbracket }\)
\(\newcommand {\LATEXunderbrace }[1]{\underbrace {#1}}\)
\(\newcommand {\LATEXoverbrace }[1]{\overbrace {#1}}\)
\(\newenvironment {matrix*}[1][]{\begin {matrix}}{\end {matrix}}\)
\(\newenvironment {pmatrix*}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bmatrix*}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bmatrix*}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vmatrix*}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vmatrix*}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newenvironment {smallmatrix*}[1][]{\begin {matrix}}{\end {matrix}}\)
\(\newenvironment {psmallmatrix*}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bsmallmatrix*}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bsmallmatrix*}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vsmallmatrix*}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vsmallmatrix*}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newenvironment {psmallmatrix}[1][]{\begin {pmatrix}}{\end {pmatrix}}\)
\(\newenvironment {bsmallmatrix}[1][]{\begin {bmatrix}}{\end {bmatrix}}\)
\(\newenvironment {Bsmallmatrix}[1][]{\begin {Bmatrix}}{\end {Bmatrix}}\)
\(\newenvironment {vsmallmatrix}[1][]{\begin {vmatrix}}{\end {vmatrix}}\)
\(\newenvironment {Vsmallmatrix}[1][]{\begin {Vmatrix}}{\end {Vmatrix}}\)
\(\newcommand {\LWRmultlined }[1][]{\begin {multline*}}\)
\(\newenvironment {multlined}[1][]{\LWRmultlined }{\end {multline*}}\)
\(\let \LWRorigshoveleft \shoveleft \)
\(\renewcommand {\shoveleft }[1][]{\LWRorigshoveleft }\)
\(\let \LWRorigshoveright \shoveright \)
\(\renewcommand {\shoveright }[1][]{\LWRorigshoveright }\)
\(\newenvironment {dcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {dcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {rcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {rcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {drcases}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {drcases*}{\begin {cases}}{\end {cases}}\)
\(\newenvironment {cases*}{\begin {cases}}{\end {cases}}\)
\(\newcommand {\MoveEqLeft }[1][]{}\)
\(\def \LWRAboxed #1!|!{\fbox {\(#1\)}&\fbox {\(#2\)}} \newcommand {\Aboxed }[1]{\LWRAboxed #1&&!|!} \)
\( \newcommand {\LWRABLines }[1][\Updownarrow ]{#1 \notag \\}\newcommand {\ArrowBetweenLines }{\ifstar \LWRABLines \LWRABLines } \)
\(\newcommand {\shortintertext }[1]{\text {#1}\notag \\}\)
\(\newcommand {\vdotswithin }[1]{\hspace {.5em}\vdots }\)
\(\newcommand {\LWRshortvdotswithinstar }[1]{\vdots \hspace {.5em} & \\}\)
\(\newcommand {\LWRshortvdotswithinnostar }[1]{& \hspace {.5em}\vdots \\}\)
\(\newcommand {\shortvdotswithin }{\ifstar \LWRshortvdotswithinstar \LWRshortvdotswithinnostar }\)
\(\newcommand {\MTFlushSpaceAbove }{}\)
\(\newcommand {\MTFlushSpaceBelow }{\\}\)
\(\newcommand \lparen {(}\)
\(\newcommand \rparen {)}\)
\(\newcommand {\ordinarycolon }{:}\)
\(\newcommand {\vcentcolon }{\mathrel {\mathop \ordinarycolon }}\)
\(\newcommand \dblcolon {\vcentcolon \vcentcolon }\)
\(\newcommand \coloneqq {\vcentcolon =}\)
\(\newcommand \Coloneqq {\dblcolon =}\)
\(\newcommand \coloneq {\vcentcolon {-}}\)
\(\newcommand \Coloneq {\dblcolon {-}}\)
\(\newcommand \eqqcolon {=\vcentcolon }\)
\(\newcommand \Eqqcolon {=\dblcolon }\)
\(\newcommand \eqcolon {\mathrel {-}\vcentcolon }\)
\(\newcommand \Eqcolon {\mathrel {-}\dblcolon }\)
\(\newcommand \colonapprox {\vcentcolon \approx }\)
\(\newcommand \Colonapprox {\dblcolon \approx }\)
\(\newcommand \colonsim {\vcentcolon \sim }\)
\(\newcommand \Colonsim {\dblcolon \sim }\)
\(\newcommand {\nuparrow }{\mathrel {\cancel {\uparrow }}}\)
\(\newcommand {\ndownarrow }{\mathrel {\cancel {\downarrow }}}\)
\(\newcommand {\bigtimes }{\mathop {\Large \times }\limits }\)
\(\newcommand {\prescript }[3]{{}^{#1}_{#2}#3}\)
\(\newenvironment {lgathered}{\begin {gathered}}{\end {gathered}}\)
\(\newenvironment {rgathered}{\begin {gathered}}{\end {gathered}}\)
\(\newcommand {\splitfrac }[2]{{}^{#1}_{#2}}\)
\(\let \splitdfrac \splitfrac \)
\(\newcommand {\LWRoverlaysymbols }[2]{\mathord {\smash {\mathop {#2\strut }\limits ^{\smash {\lower 3ex{#1}}}}\strut }}\)
\(\newcommand{\alphaup}{\unicode{x03B1}}\)
\(\newcommand{\betaup}{\unicode{x03B2}}\)
\(\newcommand{\gammaup}{\unicode{x03B3}}\)
\(\newcommand{\digammaup}{\unicode{x03DD}}\)
\(\newcommand{\deltaup}{\unicode{x03B4}}\)
\(\newcommand{\epsilonup}{\unicode{x03F5}}\)
\(\newcommand{\varepsilonup}{\unicode{x03B5}}\)
\(\newcommand{\zetaup}{\unicode{x03B6}}\)
\(\newcommand{\etaup}{\unicode{x03B7}}\)
\(\newcommand{\thetaup}{\unicode{x03B8}}\)
\(\newcommand{\varthetaup}{\unicode{x03D1}}\)
\(\newcommand{\iotaup}{\unicode{x03B9}}\)
\(\newcommand{\kappaup}{\unicode{x03BA}}\)
\(\newcommand{\varkappaup}{\unicode{x03F0}}\)
\(\newcommand{\lambdaup}{\unicode{x03BB}}\)
\(\newcommand{\muup}{\unicode{x03BC}}\)
\(\newcommand{\nuup}{\unicode{x03BD}}\)
\(\newcommand{\xiup}{\unicode{x03BE}}\)
\(\newcommand{\omicronup}{\unicode{x03BF}}\)
\(\newcommand{\piup}{\unicode{x03C0}}\)
\(\newcommand{\varpiup}{\unicode{x03D6}}\)
\(\newcommand{\rhoup}{\unicode{x03C1}}\)
\(\newcommand{\varrhoup}{\unicode{x03F1}}\)
\(\newcommand{\sigmaup}{\unicode{x03C3}}\)
\(\newcommand{\varsigmaup}{\unicode{x03C2}}\)
\(\newcommand{\tauup}{\unicode{x03C4}}\)
\(\newcommand{\upsilonup}{\unicode{x03C5}}\)
\(\newcommand{\phiup}{\unicode{x03D5}}\)
\(\newcommand{\varphiup}{\unicode{x03C6}}\)
\(\newcommand{\chiup}{\unicode{x03C7}}\)
\(\newcommand{\psiup}{\unicode{x03C8}}\)
\(\newcommand{\omegaup}{\unicode{x03C9}}\)
\(\newcommand{\Alphaup}{\unicode{x0391}}\)
\(\newcommand{\Betaup}{\unicode{x0392}}\)
\(\newcommand{\Gammaup}{\unicode{x0393}}\)
\(\newcommand{\Digammaup}{\unicode{x03DC}}\)
\(\newcommand{\Deltaup}{\unicode{x0394}}\)
\(\newcommand{\Epsilonup}{\unicode{x0395}}\)
\(\newcommand{\Zetaup}{\unicode{x0396}}\)
\(\newcommand{\Etaup}{\unicode{x0397}}\)
\(\newcommand{\Thetaup}{\unicode{x0398}}\)
\(\newcommand{\Varthetaup}{\unicode{x03F4}}\)
\(\newcommand{\Iotaup}{\unicode{x0399}}\)
\(\newcommand{\Kappaup}{\unicode{x039A}}\)
\(\newcommand{\Lambdaup}{\unicode{x039B}}\)
\(\newcommand{\Muup}{\unicode{x039C}}\)
\(\newcommand{\Nuup}{\unicode{x039D}}\)
\(\newcommand{\Xiup}{\unicode{x039E}}\)
\(\newcommand{\Omicronup}{\unicode{x039F}}\)
\(\newcommand{\Piup}{\unicode{x03A0}}\)
\(\newcommand{\Varpiup}{\unicode{x03D6}}\)
\(\newcommand{\Rhoup}{\unicode{x03A1}}\)
\(\newcommand{\Sigmaup}{\unicode{x03A3}}\)
\(\newcommand{\Tauup}{\unicode{x03A4}}\)
\(\newcommand{\Upsilonup}{\unicode{x03A5}}\)
\(\newcommand{\Phiup}{\unicode{x03A6}}\)
\(\newcommand{\Chiup}{\unicode{x03A7}}\)
\(\newcommand{\Psiup}{\unicode{x03A8}}\)
\(\newcommand{\Omegaup}{\unicode{x03A9}}\)
\(\newcommand{\alphait}{\unicode{x1D6FC}}\)
\(\newcommand{\betait}{\unicode{x1D6FD}}\)
\(\newcommand{\gammait}{\unicode{x1D6FE}}\)
\(\newcommand{\digammait}{\mathit{\unicode{x03DD}}}\)
\(\newcommand{\deltait}{\unicode{x1D6FF}}\)
\(\newcommand{\epsilonit}{\unicode{x1D716}}\)
\(\newcommand{\varepsilonit}{\unicode{x1D700}}\)
\(\newcommand{\zetait}{\unicode{x1D701}}\)
\(\newcommand{\etait}{\unicode{x1D702}}\)
\(\newcommand{\thetait}{\unicode{x1D703}}\)
\(\newcommand{\varthetait}{\unicode{x1D717}}\)
\(\newcommand{\iotait}{\unicode{x1D704}}\)
\(\newcommand{\kappait}{\unicode{x1D705}}\)
\(\newcommand{\varkappait}{\unicode{x1D718}}\)
\(\newcommand{\lambdait}{\unicode{x1D706}}\)
\(\newcommand{\muit}{\unicode{x1D707}}\)
\(\newcommand{\nuit}{\unicode{x1D708}}\)
\(\newcommand{\xiit}{\unicode{x1D709}}\)
\(\newcommand{\omicronit}{\unicode{x1D70A}}\)
\(\newcommand{\piit}{\unicode{x1D70B}}\)
\(\newcommand{\varpiit}{\unicode{x1D71B}}\)
\(\newcommand{\rhoit}{\unicode{x1D70C}}\)
\(\newcommand{\varrhoit}{\unicode{x1D71A}}\)
\(\newcommand{\sigmait}{\unicode{x1D70E}}\)
\(\newcommand{\varsigmait}{\unicode{x1D70D}}\)
\(\newcommand{\tauit}{\unicode{x1D70F}}\)
\(\newcommand{\upsilonit}{\unicode{x1D710}}\)
\(\newcommand{\phiit}{\unicode{x1D719}}\)
\(\newcommand{\varphiit}{\unicode{x1D711}}\)
\(\newcommand{\chiit}{\unicode{x1D712}}\)
\(\newcommand{\psiit}{\unicode{x1D713}}\)
\(\newcommand{\omegait}{\unicode{x1D714}}\)
\(\newcommand{\Alphait}{\unicode{x1D6E2}}\)
\(\newcommand{\Betait}{\unicode{x1D6E3}}\)
\(\newcommand{\Gammait}{\unicode{x1D6E4}}\)
\(\newcommand{\Digammait}{\mathit{\unicode{x03DC}}}\)
\(\newcommand{\Deltait}{\unicode{x1D6E5}}\)
\(\newcommand{\Epsilonit}{\unicode{x1D6E6}}\)
\(\newcommand{\Zetait}{\unicode{x1D6E7}}\)
\(\newcommand{\Etait}{\unicode{x1D6E8}}\)
\(\newcommand{\Thetait}{\unicode{x1D6E9}}\)
\(\newcommand{\Varthetait}{\unicode{x1D6F3}}\)
\(\newcommand{\Iotait}{\unicode{x1D6EA}}\)
\(\newcommand{\Kappait}{\unicode{x1D6EB}}\)
\(\newcommand{\Lambdait}{\unicode{x1D6EC}}\)
\(\newcommand{\Muit}{\unicode{x1D6ED}}\)
\(\newcommand{\Nuit}{\unicode{x1D6EE}}\)
\(\newcommand{\Xiit}{\unicode{x1D6EF}}\)
\(\newcommand{\Omicronit}{\unicode{x1D6F0}}\)
\(\newcommand{\Piit}{\unicode{x1D6F1}}\)
\(\newcommand{\Rhoit}{\unicode{x1D6F2}}\)
\(\newcommand{\Sigmait}{\unicode{x1D6F4}}\)
\(\newcommand{\Tauit}{\unicode{x1D6F5}}\)
\(\newcommand{\Upsilonit}{\unicode{x1D6F6}}\)
\(\newcommand{\Phiit}{\unicode{x1D6F7}}\)
\(\newcommand{\Chiit}{\unicode{x1D6F8}}\)
\(\newcommand{\Psiit}{\unicode{x1D6F9}}\)
\(\newcommand{\Omegait}{\unicode{x1D6FA}}\)
\(\let \digammaup \Digammaup \)
\(\renewcommand {\digammait }{\mathit {\digammaup }}\)
\(\newcommand {\smallin }{\unicode {x220A}}\)
\(\newcommand {\smallowns }{\unicode {x220D}}\)
\(\newcommand {\notsmallin }{\LWRoverlaysymbols {/}{\unicode {x220A}}}\)
\(\newcommand {\notsmallowns }{\LWRoverlaysymbols {/}{\unicode {x220D}}}\)
\(\newcommand {\rightangle }{\unicode {x221F}}\)
\(\newcommand {\intclockwise }{\unicode {x2231}}\)
\(\newcommand {\ointclockwise }{\unicode {x2232}}\)
\(\newcommand {\ointctrclockwise }{\unicode {x2233}}\)
\(\newcommand {\oiint }{\unicode {x222F}}\)
\(\newcommand {\oiiint }{\unicode {x2230}}\)
\(\newcommand {\ddag }{\unicode {x2021}}\)
\(\newcommand {\P }{\unicode {x00B6}}\)
\(\newcommand {\copyright }{\unicode {x00A9}}\)
\(\newcommand {\dag }{\unicode {x2020}}\)
\(\newcommand {\pounds }{\unicode {x00A3}}\)
\(\newcommand {\iddots }{\unicode {x22F0}}\)
\(\newcommand {\utimes }{\overline {\times }}\)
\(\newcommand {\dtimes }{\underline {\times }}\)
\(\newcommand {\udtimes }{\overline {\underline {\times }}}\)
\(\newcommand {\leftwave }{\left \{}\)
\(\newcommand {\rightwave }{\right \}}\)
\(\newcommand {\toprule }[1][]{\hline }\)
\(\let \midrule \toprule \)
\(\let \bottomrule \toprule \)
\(\newcommand {\cmidrule }[2][]{}\)
\(\newcommand {\morecmidrules }{}\)
\(\newcommand {\specialrule }[3]{\hline }\)
\(\newcommand {\addlinespace }[1][]{}\)
\(\newcommand {\LWRsubmultirow }[2][]{#2}\)
\(\newcommand {\LWRmultirow }[2][]{\LWRsubmultirow }\)
\(\newcommand {\multirow }[2][]{\LWRmultirow }\)
\(\newcommand {\mrowcell }{}\)
\(\newcommand {\mcolrowcell }{}\)
\(\newcommand {\STneed }[1]{}\)
\( \newcommand {\multicolumn }[3]{#3}\)
\(\newcommand {\tothe }[1]{^{#1}}\)
\(\newcommand {\raiseto }[2]{{#2}^{#1}}\)
\(\newcommand {\ang }[2][]{(\mathrm {#2})\degree }\)
\(\newcommand {\num }[2][]{\mathrm {#2}}\)
\(\newcommand {\si }[2][]{\mathrm {#2}}\)
\(\newcommand {\LWRSI }[2][]{\mathrm {#1\LWRSInumber \,#2}}\)
\(\newcommand {\SI }[2][]{\def \LWRSInumber {#2}\LWRSI }\)
\(\newcommand {\numlist }[2][]{\mathrm {#2}}\)
\(\newcommand {\numrange }[3][]{\mathrm {#2\,\unicode {x2013}\,#3}}\)
\(\newcommand {\SIlist }[3][]{\mathrm {#2\,#3}}\)
\(\newcommand {\SIrange }[4][]{\mathrm {#2\,#4\,\unicode {x2013}\,#3\,#4}}\)
\(\newcommand {\tablenum }[2][]{\mathrm {#2}}\)
\(\newcommand {\ampere }{\mathrm {A}}\)
\(\newcommand {\candela }{\mathrm {cd}}\)
\(\newcommand {\kelvin }{\mathrm {K}}\)
\(\newcommand {\kilogram }{\mathrm {kg}}\)
\(\newcommand {\metre }{\mathrm {m}}\)
\(\newcommand {\mole }{\mathrm {mol}}\)
\(\newcommand {\second }{\mathrm {s}}\)
\(\newcommand {\becquerel }{\mathrm {Bq}}\)
\(\newcommand {\degreeCelsius }{\unicode {x2103}}\)
\(\newcommand {\coulomb }{\mathrm {C}}\)
\(\newcommand {\farad }{\mathrm {F}}\)
\(\newcommand {\gray }{\mathrm {Gy}}\)
\(\newcommand {\hertz }{\mathrm {Hz}}\)
\(\newcommand {\henry }{\mathrm {H}}\)
\(\newcommand {\joule }{\mathrm {J}}\)
\(\newcommand {\katal }{\mathrm {kat}}\)
\(\newcommand {\lumen }{\mathrm {lm}}\)
\(\newcommand {\lux }{\mathrm {lx}}\)
\(\newcommand {\newton }{\mathrm {N}}\)
\(\newcommand {\ohm }{\mathrm {\Omega }}\)
\(\newcommand {\pascal }{\mathrm {Pa}}\)
\(\newcommand {\radian }{\mathrm {rad}}\)
\(\newcommand {\siemens }{\mathrm {S}}\)
\(\newcommand {\sievert }{\mathrm {Sv}}\)
\(\newcommand {\steradian }{\mathrm {sr}}\)
\(\newcommand {\tesla }{\mathrm {T}}\)
\(\newcommand {\volt }{\mathrm {V}}\)
\(\newcommand {\watt }{\mathrm {W}}\)
\(\newcommand {\weber }{\mathrm {Wb}}\)
\(\newcommand {\day }{\mathrm {d}}\)
\(\newcommand {\degree }{\mathrm {^\circ }}\)
\(\newcommand {\hectare }{\mathrm {ha}}\)
\(\newcommand {\hour }{\mathrm {h}}\)
\(\newcommand {\litre }{\mathrm {l}}\)
\(\newcommand {\liter }{\mathrm {L}}\)
\(\newcommand {\arcminute }{^\prime }\)
\(\newcommand {\minute }{\mathrm {min}}\)
\(\newcommand {\arcsecond }{^{\prime \prime }}\)
\(\newcommand {\tonne }{\mathrm {t}}\)
\(\newcommand {\astronomicalunit }{au}\)
\(\newcommand {\atomicmassunit }{u}\)
\(\newcommand {\bohr }{\mathit {a}_0}\)
\(\newcommand {\clight }{\mathit {c}_0}\)
\(\newcommand {\dalton }{\mathrm {D}_\mathrm {a}}\)
\(\newcommand {\electronmass }{\mathit {m}_{\mathrm {e}}}\)
\(\newcommand {\electronvolt }{\mathrm {eV}}\)
\(\newcommand {\elementarycharge }{\mathit {e}}\)
\(\newcommand {\hartree }{\mathit {E}_{\mathrm {h}}}\)
\(\newcommand {\planckbar }{\mathit {\unicode {x210F}}}\)
\(\newcommand {\angstrom }{\mathrm {\unicode {x212B}}}\)
\(\let \LWRorigbar \bar \)
\(\newcommand {\bar }{\mathrm {bar}}\)
\(\newcommand {\barn }{\mathrm {b}}\)
\(\newcommand {\bel }{\mathrm {B}}\)
\(\newcommand {\decibel }{\mathrm {dB}}\)
\(\newcommand {\knot }{\mathrm {kn}}\)
\(\newcommand {\mmHg }{\mathrm {mmHg}}\)
\(\newcommand {\nauticalmile }{\mathrm {M}}\)
\(\newcommand {\neper }{\mathrm {Np}}\)
\(\newcommand {\yocto }{\mathrm {y}}\)
\(\newcommand {\zepto }{\mathrm {z}}\)
\(\newcommand {\atto }{\mathrm {a}}\)
\(\newcommand {\femto }{\mathrm {f}}\)
\(\newcommand {\pico }{\mathrm {p}}\)
\(\newcommand {\nano }{\mathrm {n}}\)
\(\newcommand {\micro }{\mathrm {\unicode {x00B5}}}\)
\(\newcommand {\milli }{\mathrm {m}}\)
\(\newcommand {\centi }{\mathrm {c}}\)
\(\newcommand {\deci }{\mathrm {d}}\)
\(\newcommand {\deca }{\mathrm {da}}\)
\(\newcommand {\hecto }{\mathrm {h}}\)
\(\newcommand {\kilo }{\mathrm {k}}\)
\(\newcommand {\mega }{\mathrm {M}}\)
\(\newcommand {\giga }{\mathrm {G}}\)
\(\newcommand {\tera }{\mathrm {T}}\)
\(\newcommand {\peta }{\mathrm {P}}\)
\(\newcommand {\exa }{\mathrm {E}}\)
\(\newcommand {\zetta }{\mathrm {Z}}\)
\(\newcommand {\yotta }{\mathrm {Y}}\)
\(\newcommand {\percent }{\mathrm {\%}}\)
\(\newcommand {\meter }{\mathrm {m}}\)
\(\newcommand {\metre }{\mathrm {m}}\)
\(\newcommand {\gram }{\mathrm {g}}\)
\(\newcommand {\kg }{\kilo \gram }\)
\(\newcommand {\of }[1]{_{\mathrm {#1}}}\)
\(\newcommand {\squared }{^2}\)
\(\newcommand {\square }[1]{\mathrm {#1}^2}\)
\(\newcommand {\cubed }{^3}\)
\(\newcommand {\cubic }[1]{\mathrm {#1}^3}\)
\(\newcommand {\per }{/}\)
\(\newcommand {\celsius }{\unicode {x2103}}\)
\(\newcommand {\fg }{\femto \gram }\)
\(\newcommand {\pg }{\pico \gram }\)
\(\newcommand {\ng }{\nano \gram }\)
\(\newcommand {\ug }{\micro \gram }\)
\(\newcommand {\mg }{\milli \gram }\)
\(\newcommand {\g }{\gram }\)
\(\newcommand {\kg }{\kilo \gram }\)
\(\newcommand {\amu }{\mathrm {u}}\)
\(\newcommand {\nm }{\nano \metre }\)
\(\newcommand {\um }{\micro \metre }\)
\(\newcommand {\mm }{\milli \metre }\)
\(\newcommand {\cm }{\centi \metre }\)
\(\newcommand {\dm }{\deci \metre }\)
\(\newcommand {\m }{\metre }\)
\(\newcommand {\km }{\kilo \metre }\)
\(\newcommand {\as }{\atto \second }\)
\(\newcommand {\fs }{\femto \second }\)
\(\newcommand {\ps }{\pico \second }\)
\(\newcommand {\ns }{\nano \second }\)
\(\newcommand {\us }{\micro \second }\)
\(\newcommand {\ms }{\milli \second }\)
\(\newcommand {\s }{\second }\)
\(\newcommand {\fmol }{\femto \mol }\)
\(\newcommand {\pmol }{\pico \mol }\)
\(\newcommand {\nmol }{\nano \mol }\)
\(\newcommand {\umol }{\micro \mol }\)
\(\newcommand {\mmol }{\milli \mol }\)
\(\newcommand {\mol }{\mol }\)
\(\newcommand {\kmol }{\kilo \mol }\)
\(\newcommand {\pA }{\pico \ampere }\)
\(\newcommand {\nA }{\nano \ampere }\)
\(\newcommand {\uA }{\micro \ampere }\)
\(\newcommand {\mA }{\milli \ampere }\)
\(\newcommand {\A }{\ampere }\)
\(\newcommand {\kA }{\kilo \ampere }\)
\(\newcommand {\ul }{\micro \litre }\)
\(\newcommand {\ml }{\milli \litre }\)
\(\newcommand {\l }{\litre }\)
\(\newcommand {\hl }{\hecto \litre }\)
\(\newcommand {\uL }{\micro \liter }\)
\(\newcommand {\mL }{\milli \liter }\)
\(\newcommand {\L }{\liter }\)
\(\newcommand {\hL }{\hecto \liter }\)
\(\newcommand {\mHz }{\milli \hertz }\)
\(\newcommand {\Hz }{\hertz }\)
\(\newcommand {\kHz }{\kilo \hertz }\)
\(\newcommand {\MHz }{\mega \hertz }\)
\(\newcommand {\GHz }{\giga \hertz }\)
\(\newcommand {\THz }{\tera \hertz }\)
\(\newcommand {\mN }{\milli \newton }\)
\(\newcommand {\N }{\newton }\)
\(\newcommand {\kN }{\kilo \newton }\)
\(\newcommand {\MN }{\mega \newton }\)
\(\newcommand {\Pa }{\pascal }\)
\(\newcommand {\kPa }{\kilo \pascal }\)
\(\newcommand {\MPa }{\mega \pascal }\)
\(\newcommand {\GPa }{\giga \pascal }\)
\(\newcommand {\mohm }{\milli \ohm }\)
\(\newcommand {\kohm }{\kilo \ohm }\)
\(\newcommand {\Mohm }{\mega \ohm }\)
\(\newcommand {\pV }{\pico \volt }\)
\(\newcommand {\nV }{\nano \volt }\)
\(\newcommand {\uV }{\micro \volt }\)
\(\newcommand {\mV }{\milli \volt }\)
\(\newcommand {\V }{\volt }\)
\(\newcommand {\kV }{\kilo \volt }\)
\(\newcommand {\W }{\watt }\)
\(\newcommand {\uW }{\micro \watt }\)
\(\newcommand {\mW }{\milli \watt }\)
\(\newcommand {\kW }{\kilo \watt }\)
\(\newcommand {\MW }{\mega \watt }\)
\(\newcommand {\GW }{\giga \watt }\)
\(\newcommand {\J }{\joule }\)
\(\newcommand {\uJ }{\micro \joule }\)
\(\newcommand {\mJ }{\milli \joule }\)
\(\newcommand {\kJ }{\kilo \joule }\)
\(\newcommand {\eV }{\electronvolt }\)
\(\newcommand {\meV }{\milli \electronvolt }\)
\(\newcommand {\keV }{\kilo \electronvolt }\)
\(\newcommand {\MeV }{\mega \electronvolt }\)
\(\newcommand {\GeV }{\giga \electronvolt }\)
\(\newcommand {\TeV }{\tera \electronvolt }\)
\(\newcommand {\kWh }{\kilo \watt \hour }\)
\(\newcommand {\F }{\farad }\)
\(\newcommand {\fF }{\femto \farad }\)
\(\newcommand {\pF }{\pico \farad }\)
\(\newcommand {\K }{\mathrm {K}}\)
\(\newcommand {\dB }{\mathrm {dB}}\)
\(\newcommand {\kibi }{\mathrm {Ki}}\)
\(\newcommand {\mebi }{\mathrm {Mi}}\)
\(\newcommand {\gibi }{\mathrm {Gi}}\)
\(\newcommand {\tebi }{\mathrm {Ti}}\)
\(\newcommand {\pebi }{\mathrm {Pi}}\)
\(\newcommand {\exbi }{\mathrm {Ei}}\)
\(\newcommand {\zebi }{\mathrm {Zi}}\)
\(\newcommand {\yobi }{\mathrm {Yi}}\)
\(\require {mhchem}\)
\(\require {cancel}\)
\(\newcommand {\fint }{âĺŊ}\)
\(\newcommand {\hdots }{\cdots }\)
\(\newcommand {\mathnormal }[1]{#1}\)
\(\newcommand {\vecs }[2]{\vec {#1}_{#2}}\)
\(\renewcommand {\O }{\ensuremath {\mathcal {O}}}\)
\(\renewcommand {\P }{\ensuremath {\mathcal {P}}}\)
\(\newcommand {\Abl }{\ensuremath {\text {Abl}}}\)
\(\newcommand {\REG }{\ensuremath {\text {REG}}}\)
\(\newcommand {\CFL }{\ensuremath {\text {CFL}}}\)
\(\newcommand {\DCFL }{\ensuremath {\text {DCFL}}}\)
\(\newcommand {\DEA }{\ensuremath {\text {DEA}}}\)
\(\newcommand {\NEA }{\ensuremath {\text {NEA}}}\)
\(\newcommand {\DTM }{\ensuremath {\text {DTM}}}\)
\(\newcommand {\NTM }{\ensuremath {\text {NTM}}}\)
\(\newcommand {\LBA }{\ensuremath {\text {LBA}}}\)
\(\newcommand {\coLBA }{\ensuremath {\text {co-LBA}}}\)
\(\newcommand {\DLBA }{\ensuremath {\text {DLBA}}}\)
\(\newcommand {\TypNull }{\ensuremath {\text {Typ-0}}}\)
\(\newcommand {\RegExp }{\ensuremath {\text {RegExp}}}\)
\(\newcommand {\Synt }{\ensuremath {\text {Synt}}}\)
\(\newcommand {\dollar }{\ensuremath {\$}}\)
\(\newcommand {\FOR }{\ensuremath {\mathbf {for}\;}}\)
\(\newcommand {\FORALL }{\ensuremath {\mathbf {forall}\;}}\)
\(\newcommand {\REPEAT }{\ensuremath {\mathbf {repeat}\;}}\)
\(\newcommand {\UNTIL }{\ensuremath {\mathbf {until}\;}}\)
\(\newcommand {\OR }{\ensuremath {\mathbf {or}\;}}\)
\(\newcommand {\IF }{\ensuremath {\mathbf {if}\;}}\)
\(\newcommand {\THEN }{\ensuremath {\mathbf {then}\;}}\)
\(\newcommand {\ELSE }{\ensuremath {\mathbf {else}\;}}\)
\(\newcommand {\END }{\ensuremath {\mathbf {end}\;}}\)
\(\newcommand {\TO }{\ensuremath {\mathbf {to}\;}}\)
\(\newcommand {\DO }{\ensuremath {\mathbf {do}\;}}\)
\(\newcommand {\name }[1]{\textsc {#1}}\)
\(\newcommand {\smallpmatrix }[1]{\left (\begin {smallmatrix}#1\end {smallmatrix}\right )}\)
\(\newcommand {\matlab }{{\fontfamily {bch}\scshape \selectfont {}Matlab}}\)
\(\newcommand {\innerproduct }[1]{\left \langle {#1}\right \rangle }\)
\(\newcommand {\norm }[1]{\left \Vert {#1}\right \Vert }\)
\(\renewcommand {\natural }{\mathbb {N}}\)
\(\newcommand {\integer }{\mathbb {Z}}\)
\(\newcommand {\rational }{\mathbb {Q}}\)
\(\newcommand {\real }{\mathbb {R}}\)
\(\newcommand {\complex }{\mathbb {C}}\)
\(\renewcommand {\d }{\mathop {}\!\mathrm {d}}\)
\(\newcommand {\dr }{\d {}r}\)
\(\newcommand {\ds }{\d {}s}\)
\(\newcommand {\dt }{\d {}t}\)
\(\newcommand {\du }{\d {}u}\)
\(\newcommand {\dv }{\d {}v}\)
\(\newcommand {\dw }{\d {}w}\)
\(\newcommand {\dx }{\d {}x}\)
\(\newcommand {\dy }{\d {}y}\)
\(\newcommand {\dz }{\d {}z}\)
\(\newcommand {\dsigma }{\d {}\sigma }\)
\(\newcommand {\dphi }{\d {}\phi }\)
\(\newcommand {\dvarphi }{\d {}\varphi }\)
\(\newcommand {\dtau }{\d {}\tau }\)
\(\newcommand {\dxi }{\d {}\xi }\)
\(\newcommand {\dtheta }{\d {}\theta }\)
\(\newcommand {\tp }{\mathrm {T}}\)
Grammatiken
Alphabet: Eine endliche, nicht-leere Menge \(\Sigma \) heißt Alphabet.
Die Elemente von \(\Sigma \) heißen Buchstaben, Zeichen oder Terminalsymbole.
Menge \(\Sigma ^\ast \) aller Wörter: Sei \(\Sigma \) ein Alphabet. Dann ist \(\Sigma ^\ast \) die Menge aller (endlichen) Wörter, die
über \(\Sigma \) gebildet werden können (dabei ist auch das leere Wort \(\varepsilon \) zugelassen).
Ein Wort ist dabei eine endliche Folge von Buchstaben aus \(\Sigma \). Außerdem sei \(\Sigma ^+ := \Sigma ^\ast \setminus \{\varepsilon \}\).
Bemerkung: Es gibt \(1\) Wort der Länge \(0\), \(|\Sigma |\) Wörter der Länge \(1\), \(|\Sigma |^2\) Wörter der Länge \(2\) usw., d. h. \(|\Sigma |^k\)
Wörter der Länge \(k\). \(\Sigma ^\ast \) ist somit immer abzählbar unendlich.
Ein Monoid ist eine Menge mit einer Verknüpfung \(\circ \), sodass \(\forall _{a, b, c}\; (a \circ b) \circ c = a \circ (b \circ c)\)
(Assoziativität) und \(\exists _{e} \forall _{a}\; e \circ a = a \circ e = a\) (neutrales Element). Man kann daher \(\Sigma ^\ast \) auch freies Monoid über \(\Sigma \) nennen, wobei die
Grundmenge \(\Sigma \) und die Verknüpfung die Konkatenation ist (\(e\) ist das leere Wort). „Frei“ deshalb, weil sich jedes Wort aus \(\Sigma ^\ast \) auf eindeutige Weise als Verknüpfung von Buchstaben
aus \(\Sigma \) darstellen lässt.
formale Sprache: Sei \(\Sigma \) ein Alphabet. Eine Teilmenge von \(\Sigma ^\ast \) heißt formale Sprache.
Bemerkung: Aufgrund \(|\Sigma ^\ast | = \aleph _0\) ist die Kardinalität der Menge aller formalen Sprachen gleich \(\aleph _1\). Da formale Sprachen selbst auch meistens unendlich sind,
benötigt man für sie endliche Beschreibungsmöglichkeiten. Dafür dienen die Grammatiken und die Automaten.
Grammatik: Eine Grammatik ist ein \(4\)-Tupel \(G = (V, \Sigma , P, S)\), wobei
\(V\) eine endliche, nicht-leere Menge (die Menge der Variablen),
\(\Sigma \) eine endliche, nicht-leere Menge mit \(V \cap \Sigma = \emptyset \) (das Terminalalphabet),
\(P\) eine endliche Teilmenge von \((V \cup \Sigma )^+ \times (V \cup \Sigma )^\ast \)
(die Menge der Regeln oder Produktionen) und
\(S \in V\) (die Startvariable) ist.
Für \((u, v) \in P\) schreibt man auch \(u \rightarrow v\).
Satzform: Ein Wort \(w \in (V \cup \Sigma )^\ast \) heißt Satzform.
Übergangsrelation: Seien \(G = (V, \Sigma , P, S)\) eine Grammatik und \(u, v \in (V \cup \Sigma )^\ast \).
Dann sei \(u \Rightarrow _G v\), falls \(u = w_1 u_1 w_2\), \(v = w_1 u_2 w_2\) mit \(w_1, w_2 \in (V \cup \Sigma )^\ast \) und \((u_1, u_2) \in P\).
Dies definiert eine Relation \(\Rightarrow _G\) auf \((V \cup \Sigma )^\ast \), sie heißt Übergangsrelation.
\(\Rightarrow _G^\ast \) ist die reflexive und transitive Hülle von \(\Rightarrow _G\) (d. h. \(u \Rightarrow _G^\ast v\) gilt genau dann, wenn es Wörter \(w_1, \dotsc , w_k \in (V \cup
\Sigma )^\ast \), \(k \in \natural _0\) gibt mit \(u \Rightarrow _G w_1 \Rightarrow _G \dotsb \Rightarrow _G w_k \Rightarrow _G v\) oder wenn \(u = v\)).
Ableitung: Eine Folge von Wörtern \((S, w_1, \dotsc , w_k)\) mit \(w_k \in (V \cup \Sigma )^\ast \), \(k \in \natural \) und
\(S \Rightarrow _G w_1 \Rightarrow _G \dotsb \Rightarrow _G w_k\) heißt Ableitung von \(w_k\).
Linksableitung: Eine Linksableitung ist eine Ableitung, bei der immer die am weitesten links stehende Variable ersetzt wird.
(Dies ergibt nur für kontextfreie Grammatiken Sinn, d. h. falls \(P \subset V \times (V \cup \Sigma )^+\).)
erzeugte Sprache: Die von einer Grammatik \(G = (V, \Sigma , P, S)\) erzeugte Sprache ist
\(L(G) := \{w \in \Sigma ^\ast \;|\; S \Rightarrow _G^\ast w\}\).
Beispiel: \(G = (\{S\}, \{a, b\}, P, S)\) mit \(P = \{(S, ab), (S, aSb)\} = \{S \rightarrow ab \;|\; aSb\}\) (BNF) ist eine Grammatik mit \(L(G) = \{a^n b^n \;|\; n \ge 1\}\) (dies ist eine
Kurzschreibweise).
Beispiel: Für ein beliebiges Alphabet \(\Sigma \) erhält man mit \(G = (\{S\}, \Sigma , P, S\}\) und
\(P = \{S \rightarrow a \;|\; a \in \Sigma \} \cup \{S \rightarrow \varepsilon ,\; S \rightarrow SS\}\) eine Grammatik mit \(L(G) = \Sigma ^\ast \).
\(L(G) = \emptyset \) erhält man mit \(P = \emptyset \).
Beispiel: Weitere (Anwendungs-)Beispiele für Grammatiken sind natürliche Sprachen (hier nicht), korrekte arithmetische Ausdrücke (z. B. \((a + a) \cdot a\), aber nicht
\((((a((a((\) oder \((\cdot + a))(\)), Palindrome über dem Alphabet \(\{a, b\}\) (mittels \(S \rightarrow aSa \;|\; bSb \;|\; a \;|\; b \;|\; \varepsilon \)) und Wörter der Form \(a^n b^n
c^n\) (komplizierter, kontextsensitiv).
Bemerkung: Bei Maschinen ist Nichtdeterminismus meist nur von „akademischem“ Belang, bei Grammatiken ist er jedoch essentiell (eine Satzform kann verschieden abgeleitet werden).
Der einfache Pfeil \(\rightarrow \) wird für Regeln, \(\Rightarrow _G\) wird für Ableitungsschritte verwendet.
\(a^n\) ist eine Kurzform für \(a \dotsb a\) (\(n\)-mal).
Variablen werden mit Groß- und Terminalzeichen werden mit Kleinbuchstaben bezeichnet.
Chomsky-Hierarchie
Chomsky-Hierarchie:
-
Typ 0: Jede Grammatik ist vom Typ 0.
-
Typ 1: Eine Typ-0-Grammatik ist vom Typ 1 (kontextsensitiv),
falls für alle Regeln \(w_1 \rightarrow w_2\) in \(P\) gilt, dass \(|w_1| \le |w_2|\).
-
Typ 2: Eine Typ-1-Grammatik ist vom Typ 2 (kontextfrei),
falls für alle Regeln \(w_1 \rightarrow w_2\) in \(P\) gilt, dass \(w_1 \in V\).
-
Typ 3: Eine Typ-2-Grammatik ist vom Typ 3 (regulär),
falls für alle Regeln \(w_1 \rightarrow w_2\) in \(P\) gilt, dass \(w_2 \in \Sigma \cup \Sigma V\).
Eine Sprache \(L \subset \Sigma ^\ast \) heißt vom Typ \(i\), falls es eine Typ-\(i\)-Grammatik \(G\) gibt mit \(L(G) = L\) (\(i = 0, \dotsc , 3\)).
Bemerkung: Die Ableitungen einer Typ-3-Grammatik haben die Form \(S \Rightarrow a_1 A_1 \Rightarrow a_1 a_2 A_2\)
\(\Rightarrow \dotsb \Rightarrow a_1 \dotsb a_n A_n\). Weiter geht es mit \(a_1 \dotsb a_n a_{n+1} A_{n+1}\), terminiert wird mit \(a_1 \dotsb a_n a_{n+1}\).
Bei Typ-0-Grammatiken kann die Satzform beim Ableiten länger und wieder kürzer werden, bei Typ-1-Grammatiken ist dagegen die Länge der Satzform monoton steigend, daher heißen
Typ-1-Grammatiken auch nicht-verkürzend. Das leere Wort \(\varepsilon \) kann von diesen Grammatiken nie erzeugt werden (für alle \(w_1 \rightarrow
w_2\) in \(P\) gilt, dass \(1 \le |w_1| \le |w_2|\)).
\(\varepsilon \)-Sonderregel: Für Typ-1-Grammatiken kann \(S \rightarrow \varepsilon \) zugelassen werden.
In diesem Fall ist aber \(S\) auf allen rechten Seiten verboten.
Bemerkung: \(S\) ist auf allen rechten Seiten verboten, weil sonst die Definition der Typ-1-Grammatik sinnlos werden würde: Man könnte z. B. eine Regel der Form \(AB \rightarrow CSS\)
basteln, die wegen \(S \rightarrow \varepsilon \) als \(AB \rightarrow C\) angewendet werden könnte.
Damit obige Definition sinnvoll ist, sollte man zeigen, dass es zu jeder Typ-\(i\)-Grammatik
\(G = (V, \Sigma , P, S)\) eine Typ-\(i\)-Grammatik \(G’\) mit \(\varepsilon \)-Sonderregel gibt, sodass \(L’ = L \cup \{\varepsilon \}\) mit \(L’ := L(G’)\) und \(L := L(G)\) (\(i = 1, 2, 3\)), d. h.
man kann jede Grammatik bei zugelassener \(\varepsilon \)-Sonderregel so verändern, dass ihre Sprache nur um das leere Wort ergänzt wird.
Für Typ-1-Grammatiken verfährt man, indem man \(G’ = (V’, \Sigma , P’, S)\) setzt mit \(V’ = V \cup \{S’\}\) und \(S’ \notin V\). \(P’\) erhält man aus \(P\), indem man in allen Regeln
\(S\) durch \(S’\) ersetzt und die Regeln \(S \rightarrow S’\), \(S \rightarrow \varepsilon \) hinzufügt.
Für Typ-2-Grammatiken kann man genauso verfahren, da die hinzugefügten Regeln (insbesondere \(S \rightarrow S’\)) Typ-2-konform sind.
Bei Typ-3-Grammatiken ergibt sich das Problem, dass \(S \rightarrow S’\) keine Typ-3-Regel ist. Man verfährt stattdessen folgendermaßen, um \(P’\) aus \(P\) zu erhalten:
ersetze in allen Regeln \(S\) durch \(S’\)
für jede Regel mit \(S’\) auf der linken Seite füge dieselbe Regel mit \(S\) auf der linken Seite hinzu
füge \(S \rightarrow \varepsilon \) hinzu
Es ergibt sich eine Grammatik \(G’\) gleichen Typs (bis auf \(\varepsilon \)-Sonderregel) mit \(L(G’) = L(G) \cup \{\varepsilon \}\).
Bemerkung: Eine Typ-1-Sprache, die durch eine Typ-1-Grammatik (die keine Typ-3-Grammatik ist) erzeugt wird, kann auch vom Typ 3 sein.
Bemerkung: Die Chomsky-Hierarchie hat ihren Namen von der Anordnung der Sprachenmengen. In der Menge aller Sprachen bilden die Typ-0-Sprachen eine echte Teilmenge, die die entscheidbaren Sprachen wieder als
echte Teilmenge beinhalten. Diese enthalten in echter Inklusion die Typ-1-Sprachen (kontextsensitive Sprachen), die in echter Inklusion die Typ-2-Sprachen beinhalten (kontextfreie Sprachen), die in echter Inklusion die
Typ-3-Sprachen beinhalten (reguläre Sprachen).
Wortproblem
Wortproblem: Gegeben seien eine Grammatik \(G = (V, \Sigma , P, S)\) und ein Wort \(w \in \Sigma ^\ast \). Gesucht ist ein Algorithmus, der beliebige \(G\) und \(w\) als Eingabe hat sowie \(1\)
ausgibt, falls \(w \in L(G)\), und \(0\), falls \(w \notin L(G)\) (d. h. der Algorithmus implementiert die charakteristische Funktion von \(L(G)\) auf \(\Sigma ^\ast \)). Dieses Problem heißt Wortproblem.
Satz (Wortproblem entscheidbar für Typ-1-Sprachen): Das Wortproblem ist für Sprachen vom Typ 1 entscheidbar, d. h. der
gesuchte Algorithmus existiert (falls die Sprache durch eine Typ-1-Grammatik gegeben ist).
Bemerkung: Sprachen vom Typ 2 und Typ 3 sind auch vom Typ 1, d. h. das Wortproblem ist auch hier entscheidbar. Für Typ-0-Sprachen ist das Wortproblem i. A. nicht entscheidbar.
Beweis: Als Beweis wird ein Algorithmus angegeben.
Seien also \(G = (V, \Sigma , P, S)\) eine Typ-1-Grammatik und \(x \in \Sigma ^\ast \) mit \(n := |x| \ge 1\).
\(\seteqnumber{0}{}{0}\)
\begin{align*}
&T := \{S\}\\ &\REPEAT T_1 := T;\; T := \Abl _n(T)\\ &\UNTIL (x \in T) \;\OR (T = T_1);\\ &\IF x \in T \;\THEN \text {output}(1) \;\ELSE \text {output}(0);
\end{align*}
Für eine Menge \(X \subset (V \cup \Sigma )^\ast \) ist dabei \(\Abl _n(X)\) definiert als
\(\Abl _n(X) := X \cup \{w \in (V \cup \Sigma )^\ast \;|\; (|w| \le n) \land (\exists _{w’ \in X}\; w’ \Rightarrow _G w)\}\).
Der Algorithmus terminiert stets (d. h. er bricht für jede Eingabe nach einer endlichen Anzahl von Schritten ab), denn: Aufgrund \(X \subset \Abl _n(X)\) gilt am Ende jedes Schleifendurchlaufs entweder \(T_1
= \Abl _n(T_1)\) (dann wird terminiert) oder es gilt \(T_1 \subsetneqq \Abl _n(T_1)\).
Der letzte Fall ist jedoch nur endlich oft möglich, da dabei \(|T_1| < |\Abl _n(T_1)|\) gilt, aber \(|\Abl _n(T_1)|\) nach oben durch \(\sum _{i=1}^n t^i\) mit \(t = |V \cup \Sigma |\) beschränkt
ist. Somit terminiert der Algorithmus nach endlich vielen Schritten.
Der Algorithmus ist korrekt (d. h. er gibt \(1\) aus genau dann, wenn \(x \in L(G)\)), denn:
Ist \(x \in T\) im \(r\)-ten Schritt (das soll bedeuten, dass \(x \notin T\) für vorherige Schritte gilt), so gibt es ein \(w_1 \in (V \cup \Sigma )^+\) mit \(w_1 \in T\) im \((r - 1)\)-ten Schritt und \(w_1
\Rightarrow _G x\). Daraus folgt, dass es ein \(w_2 \in (V \cup \Sigma )^+\) gibt mit \(w_2 \in T\) im \((r - 2)\)-ten Schritt und \(w_2 \Rightarrow _G w_1\) usw.
Induktiv gibt es also ein \(w_{r-1} \in (V \cup \Sigma )^+\) mit \(w_{r-1} \in T\) im ersten Schritt und \(w_{r-1} \Rightarrow _G w_{r-2}\). Daraus folgt wieder, dass es ein \(w_r \in (V \cup \Sigma )^+\) mit \(w_r
\in T\) im nullten Schritt und \(w_r \Rightarrow _G w_{r-1}\). Im nullten Schritt ist allerdings \(T = \{S\}\), d. h. es gilt \(w_r = S\).
Insgesamt gilt also \(S = w_r \Rightarrow _G w_{r-1} \Rightarrow _G \dotsb \Rightarrow _G w_2 \Rightarrow _G w_1 \Rightarrow _G x\), also \(x \in L(G)\). Wenn der Algorithmus \(1\) ausgibt, dann ist daher \(x
\in L(G)\). Die andere Richtung überlegt man sich analog, es gilt also \(x \in T\) im \(r\)-ten Schritt genau dann, wenn \(S \Rightarrow _G^\ast x\) in \(r\) Schritten.
Syntaxbäume
Syntaxbaum: Sei eine Typ-2-Grammatik \(G = (V, \Sigma , P, S)\) gegeben. Jeder Ableitung eines Wortes \(x \in L(G)\) kann man einen Syntaxbaum oder
Ableitungsbaum zuordnen:
Sei dazu \(S = x_0 \Rightarrow _G x_1 \Rightarrow _G \dotsb \Rightarrow _G x_n = x\) eine Ableitung des Wortes \(x \in L(G)\). Man ordnet der Wurzel des (zu konstruierenden) Syntaxbaums die Startvariable \(S\)
zu. Für \(i = 1, \dotsc , n\) führe man folgendes durch: Falls im \(i\)-ten Ableitungsschritt \(x_{i-1} \Rightarrow _G x_i\) die Variable \(A\) mit der Regel \(A \rightarrow z \in P\) durch ein Wort
\(z\) ersetzt wird, erstelle im Syntaxbaum \(|z|\) Söhne von \(A\) und beschrifte diese mit den einzelnen Zeichen von \(z\). Auf diese Weise entsteht ein Baum, dess Blätter gerade mit den Zeichen in \(x\)
beschriftet sind.
Bemerkung: Syntaxbäume für Typ-3-Grammatiken sind immer entartet, d. h. jeder Knoten hat höchstens zwei Söhne (davon immer ein Terminalzeichen und evtl. eine
Variable).
Syntaxbäume für Grammatiken, die nicht vom Typ 2 sind, sind nicht sinnvoll definiert.
Bemerkung: Verschiedenen Ableitungen eines Wortes \(x \in L(G)\) kann derselbe Syntaxbaum zugeordnet sein (beispielsweise indem man die Ableitungsreihenfolge variiert). Ersetzt man immer die erste vorkommende
(am weitesten links stehende) Variable, so spricht man von einer Linksableitung. Weil man jedem Syntaxbaum eindeutig eine Linksableitung zuordnen kann, gibt es für jedes
Wort \(x \in L(G)\) eine Linksableitung.
Bemerkung: Verschiedenen Syntaxbäumen eines Wortes können verschiedene Bedeutungen zugewiesen werden. Man denke dabei an die Sprache der arithmetischen Ausdrücke, in der es
einen Sinn ergeben würde, implizit Klammern um den zuletzt abgeleiteten Term zu setzen. Man würde also den zuletzt abgeleiteten Term zuerst ausrechnen. Solche Interpetationen sind z. B. im
Compilerbau sinnvoll. Hier wird dieser Aspekt nicht weiter verfolgt.
eindeutig/mehrdeutig: Eine Typ-2-Grammatik \(G\) heißt mehrdeutig, falls es ein Wort
\(x \in L(G)\) gibt, dass mindestens zwei Ableitungen besitzt, deren Syntaxbäume verschieden sind. Sonst heißt die Grammatik eindeutig (jedes Wort \(x \in L(G)\)
besitzt genau einen Syntaxbaum).
Bemerkung: Es kann sein, dass es für eine Sprache mehrere die Sprache erzeugende Grammatiken gibt, von denen eine mehrdeutig und eine eindeutig ist.
inhärent mehrdeutig: Eine Typ-2-Sprache \(L\) heißt inhärent mehrdeutig, falls jede Typ-2-Grammatik \(G\) mit \(L(G) = L\) mehrdeutig
ist.
Bemerkung: Im Allgemeinen ist es algorithmisch unmöglich festzustellen, ob eine Typ-2-Grammatik mehrdeutig (oder ob eine Typ-2-Sprache inhärent mehrdeutig) ist oder nicht.
Backus-Naur-Form (BNF): Backus und Naur führten einen Formalismus zum kompakten Aufschreiben von Typ-2-Grammatiken ein
(Backus-Naur-Form (BNF)).
In Grammatiken \(G\) bedeutet die Regel \(A \rightarrow \beta _1 \;|\; \beta _2 \;|\; \dotsb \;|\; \beta _n\) den Satz von Regeln
\(A \rightarrow \beta _1\), \(A \rightarrow \beta _2\), …, \(A \rightarrow \beta _n\). (Man kann statt \(\rightarrow \) auch \(::=\) schreiben.)
erweiterte Backus-Naur-Form (EBNF): Verwendet man zusätzliche Notationen, so spricht man von der erweiterten Backus-Naur-Form (EBNF).
In Grammatiken \(G\) steht die Regel \(A \rightarrow \alpha [\beta ] \gamma \) für die Regeln \(A \rightarrow \alpha \gamma \), \(A \rightarrow \alpha \beta \gamma \).
Die Regel \(A \rightarrow \alpha \{\beta \} \gamma \) steht für die Regeln \(A \rightarrow \alpha \gamma \), \(A \rightarrow \alpha B \gamma \), \(B \rightarrow \beta \), \(B \rightarrow \beta
B\).
Bemerkung: Da (E)BNF und kontextfreie Grammatiken gleichwertig sind, können durch
(E)BNF genau die kontextfreien Sprachen dargestellt werden.