字串（string）

字串是依固定順序一個接一個寫下的有限符號序列，像串在鐵絲上、有確定次序的珠子。若你的字母表是 {a, b}，那麼 aab 就是一個字串：先一個 a、再一個 a、再一個 b。順序重要，所以 aab 和 aba 是不同的字串，即使用的是相同的符號。字串正是你寫下輸入時所打出的東西：一排字母。

形式上，字母表 Σ 上的字串（常也稱為字／詞）是由 Σ 中符號構成的有限有序序列。我們通常用 w、x、y、z 這類字母來命名字串。字串有確定的長度（其中符號的個數），也有確定的第一個符號、第二個符號等等。允許重複：aaa 是完全合格的字串。還有一個完全沒有符號的特別字串，稱為空字串，我們會另外介紹。關鍵在於：字串必須有限，它有最後一個符號，即使非常長。

字串是整門學科的通用貨幣。有限自動機的輸入是字串，文法生成的東西是字串，一個問題會變成一個字串集合。因為字串只是「有序的有限序列」，只要固定好字母表，同一個概念就能描述一個二進位檔、一個句子、一段 DNA，或一行程式碼。正是這種一致性，讓理論能夠一次談論所有的計算。