Prázdný řetězec - Empty string

V teorii formálního jazyka je prázdný řetězec nebo prázdné slovo jedinečný řetězec délky nula.

Formální teorie

Formálně je řetězec konečným uspořádaným sledem znaků, jako jsou písmena, číslice nebo mezery. Prázdný řetězec je speciální případ, kdy má sekvence délku nula, takže v řetězci nejsou žádné symboly. Je pouze jeden prázdný řetězec, protože dva řetězce se liší pouze v případě, že mají různé délky nebo jinou posloupnost symbolů. Při formálních úpravách je prázdný řetězec označen ε nebo někdy Λ nebo λ .

Prázdný řetězec by neměl být zaměňován s prázdným jazykem ∅ , což je formální jazyk (tj. Sada řetězců), který neobsahuje žádné řetězce, dokonce ani prázdný řetězec.

Prázdný řetězec má několik vlastností:

• | ε | = 0. Délka řetězce je nula.
• ε ⋅ s = s ⋅ ε = s. Prázdný řetězec je element identity ze zřetězení operací. Sada všech řetězců tvoří volný monoid s ohledem na ⋅ a ε.
• ε ^R = ε. Obrácení prázdného řetězce vytvoří prázdný řetězec.
• Prázdný řetězec předchází jakémukoli jinému řetězci v lexikografickém pořadí , protože je nejkratší ze všech řetězců.

V bezkontextových gramatikách je produkční pravidlo, které umožňuje symbolu produkovat prázdný řetězec, známé jako ε-produkce a o symbolu se říká, že je „s možnou hodnotou null“.

Použití v programovacích jazycích

Ve většině programovacích jazyků jsou řetězce datovým typem . Řetězce jsou obvykle uloženy na odlišných paměťových místech . To znamená, že stejný řetězec (například prázdný řetězec) může být uložen na dvou nebo více místech v paměti.

Tímto způsobem by mohlo být v paměti více prázdných řetězců, na rozdíl od definice formální teorie, pro kterou existuje pouze jeden možný prázdný řetězec. Funkce porovnání řetězců by však naznačovala, že všechny tyto prázdné řetězce jsou si navzájem stejné.

I řetězec s nulovou délkou může vyžadovat paměť k uložení, v závislosti na použitém formátu. Ve většině programovacích jazyků je prázdný řetězec odlišný od nulového odkazu (nebo nulového ukazatele), protože nulový odkaz neodkazuje na žádný řetězec, dokonce ani na prázdný řetězec. Prázdný řetězec je legitimní řetězec, na kterém by měla fungovat většina řetězcových operací. Některé jazyky zacházejí s některými nebo všemi následujícími podobnými způsoby: prázdné řetězce, nulové odkazy, celé číslo 0, číslo s plovoucí desetinnou čárkou, logická hodnota false , znak ASCII NUL nebo jiné podobné hodnoty.

Prázdný řetězec je obvykle reprezentován podobně jako ostatní řetězce. V implementacích se znakem ukončujícím řetězec (řetězce s nulovým zakončením nebo řádky prostého textu) je prázdný řetězec indikován okamžitým použitím tohoto ukončovacího znaku.

Příklady prázdných řetězců

Prázdný řetězec je syntakticky platnou reprezentací nuly v pozičním zápisu (v jakékoli bázi), který neobsahuje úvodní nuly . Protože prázdný řetězec nemá standardní vizuální reprezentaci mimo formální jazykovou teorii, je místo toho číslo nula tradičně reprezentováno jednou desetinnou číslicí 0 .

Nulová paměť, interpretovaná jako řetězec zakončený nulou , je prázdný řetězec.

Prázdné řádky textu ukazují prázdný řetězec. K tomu může dojít ze dvou po sobě jdoucích EOL , jak se často vyskytuje v textových souborech , a to se někdy používá při zpracování textu k oddělení odstavců , např. V MediaWiki .

Viz také

• Prázdná sada
• Řetězec zakončený nulou
• Teorie zřetězení

Reference