文字列(コンピュータサイエンス)

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
コンピューティングにおける文字列データの図。 「これは文字列です!」という文を表示します  各文字を別々のボックスに入れます。 「文字列」という言葉は上にあり、文全体を指します。 「キャラクター」というラベルは下にあり、個々のボックスを指しています。
文字列は多くの場合、文字で構成されています。これらは、文などの人間が読めるデータや、DNA核酸配列などのアルファベット順のデータのリストを保存するのに役立ちます。

コンピュータプログラミングでは文字列は伝統的に文字でありリテラル定数またはある種の変数として使用されます。後者では、要素を変更して長さを変更したり、(作成後に)固定したりできます。文字列は一般にデータ型と見なされ、多くの場合、文字エンコードを使用して要素のシーケンス(通常は文字)を格納するバイト(またはワード)の配列データ構造として実装されます文字列は、より一般的な配列を示す場合もありますまたは他のシーケンス(またはリスト)のデータ型と構造。

使用するプログラミング言語と正確なデータ型に応じて、文字列として宣言された変数により、メモリ内のストレージが所定の最大長に静的に割り当てられるか、動的割り当てを使用して可変数の要素を保持できるようになります。

文字列がソースコードに文字通り現れる場合、それは文字列リテラルまたは匿名文字列として知られています。[1]

数理論理学理論計算機科学で使用される形式言語では、文字列はアルファベットと呼ばれるセットから選択される記号の有限シーケンスです

文字列データ型

文字列データ型は、正式な文字列の概念に基づいてモデル化されたデータ型です。文字列は非常に重要で有用なデータ型であるため、ほぼすべてのプログラミング言語で実装されています。一部の言語では、プリミティブ型として使用でき、他の言語では複合型として使用できますほとんどの高級プログラミング言語構文では、通常は何らかの方法で引用符で囲まれた文字列を使用して、文字列データ型のインスタンスを表すことができます。このようなメタ文字列は、リテラルまたは文字列リテラルと呼ばれます。

文字列の長さ

正式な文字列は任意の有限の長さを持つことができますが、実際の言語の文字列の長さは、多くの場合、人為的な最大値に制限されます。一般に、文字列データ型には2つのタイプがあります。コンパイル時に決定される固定最大長を持ち、この最大が必要かどうかに関係なく同じ量のメモリを使用する固定文字列と、可変長文字列です。その長さは任意に固定されておらず、実行時の実際の要件に応じてさまざまな量のメモリを使用できます(メモリ管理を参照)。最新のプログラミング言語のほとんどの文字列は可変長文字列です。もちろん、可変長の文字列でさえ、利用可能なサイズによって長さが制限されますコンピュータメモリ文字列の長さは、個別の整数(長さに別の人為的な制限を課す可能性があります)として、または終了文字(通常はCプログラミング言語のようにすべてビットがゼロの文字値)を介して暗黙的に格納できます。以下の「ヌル終了」も参照してください

文字エンコード

文字列データ型は、歴史的に文字ごとに1バイトを割り当ててきました。正確な文字セットは地域によって異なりますが、文字エンコードはプログラムが特別に処理する文字(ピリオド、スペース、コンマなど)であるため、プログラマーがこれを無視することを回避できるほど類似しています。 )プログラムが遭遇するすべてのエンコーディングで同じ場所にありました。これらの文字セットは通常、 ASCIIまたはEBCDICに基づいていましたあるエンコーディングのテキストが別のエンコーディングを使用するシステムで表示された場合、テキストはしばしばマングルされましたが、多くの場合、ある程度読みやすく、一部のコンピュータユーザーはマングルされたテキストを読むことを学びました。

中国語日本語韓国語(総称してCJKと呼ばれる)などのロゴ言語、適切な表現のために256文字(1文字あたり1つの8ビットバイトのエンコードの制限)をはるかに超える必要があります。通常の解決策は、ASCIIのシングルバイト表現を維持し、CJK表意文字の2バイト表現を使用することでした。これらを既存のコードで使用すると、文字列の照合と切断に問題が発生し、その重大度は文字エンコードの設計方法によって異なります。EUCなどの一部のエンコーディングファミリは、ASCII範囲のバイト値がそのASCII文字のみを表すことを保証し、これらの文字をフィールド区切り文字として使用するシステムでエンコードを安全にします。ISO-2022Shift-JISなどの他のエンコーディングはそのような保証を行わないため、バイトコードの照合は安全ではありません。これらのエンコーディングも「自己同期」ではなかったため、文字列の先頭までバックアップする必要がある文字境界を特定し、2つの文字列を一緒に貼り付けると、2番目の文字列が破損する可能性がありました。

Unicodeは、全体像をいくらか単純化しました。現在、ほとんどのプログラミング言語にはUnicode文字列のデータ型があります。Unicodeで推奨されるバイトストリーム形式UTF-8は、古いマルチバイトエンコーディングで上記の問題が発生しないように設計されています。UTF-8、UTF-16、およびUTF-32では、固定サイズのコード単位が「文字」とは異なることをプログラマーが知っている必要があります。現在の主な問題は、この違いを隠そうとする誤って設計されたAPIです(UTF-32はコードポイントを固定サイズにしますが、コードを構成するため、これらは「文字」ではありません)。

実装

C ++PerlRuby などの一部の言語では、通常、文字列の作成後に文字列の内容を変更できます。これらは可変文字列と呼ばれます。JavaJavaScriptLuaPythonGoなどの他の言語では、値は固定されており、変更を加える場合は新しい文字列を作成する必要があります。これらは不変の文字列と呼ばれます。不変の文字列を持つこれらの言語の一部は、Javaや.NETStringBuilder、スレッドセーフなJava StringBufferCocoaなど、変更可能な別のタイプも提供します。 NSMutableString不変性には長所と短所の両方があります。不変の文字列は多くのコピーを非効率的に作成する必要があるかもしれませんが、それらはより単純で完全にスレッドセーフです。

文字列は通常、バイト、文字、またはコードユニットの配列として実装され、個々のユニットまたはサブストリング(固定長の場合は文字を含む)に高速にアクセスできるようにします。Haskellなどのいくつかの言語は、代わりにリンクリストとしてそれらを実装します

PrologErlangなどの一部の言語では、専用の文字列データ型の実装をまったく避け、代わりに文字列を文字コードのリストとして表す規則を採用しています。

表現

文字列の表現は、文字レパートリーの選択と文字エンコードの方法に大きく依存します。古い文字列の実装は、ASCIIで定義されたレパートリーとエンコーディング、またはISO8859シリーズなどの最近の拡張機能で動作するように設計されています。最近の実装では、Unicodeで定義された広範なレパートリーと、UTF-8やUTF-16などのさまざまな複雑なエンコーディングを使用することがよくあります。

バイト文字列という用語は通常、(読み取り可能な)文字のみの文字列やビットの文字列などではなく、汎用のバイト文字列を示します。多くの場合、バイト文字列は、バイトが任意の値を取り、任意のデータをそのまま保存できることを意味します。つまり、終了値として解釈される値があってはなりません。

ほとんどの文字列の実装は、対応する文字の文字コードを格納するエントリを持つ可変長配列に非常に似ています。主な違いは、特定のエンコーディングでは、単一の論理文字が配列内の複数のエントリを占める場合があることです。これは、たとえばUTF-8で発生します。この場合、単一のコード(UCSコードポイント)は1〜4バイトの範囲で使用でき、単一の文字は任意の数のコードを使用できます。このような場合、文字列の論理的な長さ(文字数)は、配列の物理的な長さ(使用中のバイト数)とは異なります。UTF-32は、問題の最初の部分を回避します。

ヌル終了

文字列の長さは、特殊な終了文字を使用して暗黙的に格納できます。多くの場合、これはヌル文字(NUL)であり、すべてのビットがゼロであり、一般的なCプログラミング言語で使用および永続化されている規則です。[2]したがって、この表現は一般にC文字列と呼ばれます。このn文字の文字列の表現は、n + 1スペース(ターミネータの場合は1)を使用するため、暗黙のデータ構造になります。

終了文字列では、終了コードはどの文字列でも許可される文字ではありません。長さフィールドを持つ文字列にはこの制限がなく、任意のバイナリデータを格納することもできます。

10バイトのバッファに格納されたnullで終了する文字列の例と、8ビットの16進数としてのASCII(または最新のUTF-8 )表現は次のとおりです。

F R A N K NUL k e f w
46 16 52 16 41 16 4E 16 4B 16 00 16 6B 16 65 16 66 16 77 16

上記の例の文字列 " FRANK"の長さは5文字ですが、6バイトを占めます。ターミネータの後の文字は、表現の一部を形成しません。それらは他のデータの一部であるか、単なるゴミである可能性があります。(この形式の文字列は、宣言に使用された元のアセンブリ言語ディレクティブ にちなんで、ASCIZ文字列と呼ばれることもあります。)

バイトおよびビットで終了

文字列を終了するためにnull以外の特別なバイトを使用することは、歴史的にハードウェアとソフトウェアの両方で使用されてきましたが、印刷文字でもある値を使用することもありました。$多くのアセンブラシステムで:使用され、CDCシステムで使用され(この文字の値はゼロ)、ZX80はBASIC言語の文字列区切り文字であるため "[3]を使用しました。

IBM 1401のような「データ処理」マシンは、特殊なワードマークビットを使用して左側の文字列を区切り、右側から操作を開始します。このビットは、文字列の他のすべての部分でクリアする必要がありました。つまり、IBM 1401には7ビットのワードがありましたが、これを機能として使用し、(たとえば)ASCIIコードを処理するために7番目のビットの割り当てをオーバーライドすることを考えた人はほとんどいませんでした。

初期のマイクロコンピュータソフトウェアは、ASCIIコードが上位ビットを使用しないという事実に依存しており、文字列の終わりを示すように設定していました。出力する前に0にリセットする必要があります。[4]

長さプレフィックス

文字列の長さは、たとえば文字列の前にバイト値として長さを付けることにより、明示的に格納することもできます。この規則は、多くのPascal方言で使用されています。結果として、一部の人々はそのような文字列をPascal文字列またはP文字列と呼びます。文字列の長さをバイトとして保存すると、最大文字列長が255に制限されます。このような制限を回避するために、P文字列の改善された実装では、16ビット、32ビット、または64ビットの単語を使用して文字列の長さを保存します。長さフィールドがアドレス空間をカバーする場合、文字列は使用可能なメモリによってのみ制限されます

長さが制限されている場合は、一定のスペース(通常はマシンワード)でエンコードできるため、n + kスペースを取る暗黙のデータ構造になります。ここで、 kはワード内の文字数です(8ビットの場合は8)。 64ビットマシンではASCII、32ビットマシンでは32ビットUTF-32 / UCS-4の場合は1など)。長さが制限されていない場合、長さnをエンコードするとlog(n)スペースが必要になるため(固定長コードを参照)、長さ接頭辞付きの文字列は簡潔データ構造であり、log(n)+ nスペースで長さnの文字列をエンコードします

後者の場合、長さプレフィックスフィールド自体の長さが固定されていないため、文字列が大きくなったときに実際の文字列データを移動して、長さフィールドを増やす必要があります。

以下は、10バイトのバッファに格納されているPascal文字列とそのASCII / UTF-8表現です。

長さ F R A N K k e f w
05 16 46 16 52 16 41 16 4E 16 4B 16 6B 16 65 16 66 16 77 16

レコードとしての文字列

オブジェクト指向言語を含む多くの言語は、次のような内部構造を持つ レコードとして文字列を実装します。

クラス 文字列{ 
  size_t長さ; 
  char * text ; 
};

ただし、実装は通常非表示であるため、文字列はメンバー関数を介してアクセスおよび変更する必要があります。text動的に割り当てられたメモリ領域へのポインタであり、必要に応じて拡張できます。文字列(C ++)も参照してください

その他の表現

文字終了と長さコードの両方で文字列が制限されます。たとえば、ヌル(NUL)文字を含むC文字配列は、C文字列ライブラリ関数で直接処理できません。長さコードを使用する文字列は、長さコードの最大値に制限されます。

これらの制限は両方とも、巧妙なプログラミングによって克服できます。

文字の終了に関連する問題がなく、原則として長さコードの境界を克服できるデータ構造とそれらを操作する関数を作成することが可能です。ランレングスエンコーディング(繰り返される文字を文字値と長さで置き換える)およびハミングエンコーディング[説明が必要]の手法を使用して表現される文字列を最適化することもできます。

これらの表現は一般的ですが、他の表現も可能です。ロープを使用すると、挿入、削除、連結などの特定の文字列操作がより効率的になります。

テキストエディタのコアデータ構造は、編集中のファイルの現在の状態を表す文字列(文字のシーケンス)を管理するものです。その状態は単一の長い連続した文字配列に格納できますが、通常のテキストエディタでは、代わりにシーケンスデータ構造として代替表現(ギャップバッファ、行のリンクリストピーステーブル、またはロープ)を使用します。挿入、削除、以前の編集の取り消しなどの特定の文字列操作がより効率的になります。[5]

セキュリティ上の懸念

文字列のメモリレイアウトとストレージ要件が異なると、文字列データにアクセスするプログラムのセキュリティに影響を与える可能性があります。終了文字を必要とする文字列表現は、コーディングエラーまたは攻撃者が意図的にデータを変更したことが原因で終了文字が存在しない場合、通常、バッファオーバーフローの問題が発生しやすくなります。別の長さフィールドを採用する文字列表現も、長さを操作できる場合は影響を受けやすくなります。このような場合、文字列データにアクセスするプログラムコードでは、文字列メモリの制限外のデータに誤ってアクセスしたり変更したりしないように、 境界チェックが必要です。

文字列データは、プログラムへのユーザー入力から頻繁に取得されます。そのため、文字列を検証して、期待される形式を表していることを確認するのはプログラムの責任です。ユーザー入力の検証を制限するか、まったく実行しないと、プログラムがコードインジェクション攻撃に対して脆弱になる可能性があります。

リテラル文字列

場合によっては、文字列は、人間が読める形式であり、マシンで使用することを目的としたテキストファイル内に埋め込む必要があります。これは、たとえば、プログラミング言語のソースコードや構成ファイルで必要になります。この場合、NUL文字は通常は非表示(印刷不可)であり、キーボードからの入力が難しいため、ターミネーターとしては機能しません。文字列の長さを保存することも、手動での計算と長さの追跡が面倒でエラーが発生しやすいため、不便です。

2つの一般的な表現は次のとおりです。

非テキスト文字列

文字列は文字列の非常に一般的な使用法ですが、コンピュータサイエンスの文字列は、一般的に、同種の型が付けられたデータの任意のシーケンスを指す場合があります。たとえば、ビット文字列またはバイト文字列を使用して、通信媒体から取得された非テキストのバイナリデータを表すことができます。このデータは、アプリケーションのニーズ、プログラマーの要望、および使用されているプログラミング言語の機能に応じて、文字列固有のデータ型で表される場合とされない場合があります。プログラミング言語の文字列実装が8ビットクリーンでない場合、データが破損する可能性があります。

Cプログラマーは、定義上常にnullで終了する「文字列」(別名​​「文字列」)と、同じ配列に格納される可能性があるが「疑似文字列」である「バイト文字列」または「疑似文字列」を明確に区別します。多くの場合、nullで終了しません。このような「バイト文字列」でC文字列処理関数を使用すると、うまくいくように見えることがよくありますが、後でセキュリティの問題が発生します。[6] [7] [8]

文字列処理アルゴリズム

文字列を処理するためのアルゴリズムは多数あり、それぞれにさまざまなトレードオフがあります。競合するアルゴリズムは、実行時間、ストレージ要件などに関して 分析できます。

アルゴリズムのいくつかのカテゴリは次のとおりです。

高度な文字列アルゴリズムは、多くの場合、複雑なメカニズムとデータ構造を採用しています。その中には、接尾辞木有限状態マシンが含まれます。

文字列の名前は、文字列処理に使用されるアルゴリズムとデータ構造の問題のために、コンピューター科学者のZviGalilによって1984年に造られました[9] [サードパーティのソースが必要]

文字列指向の言語とユーティリティ

文字列は非常に便利なデータ型であるため、文字列処理アプリケーションを簡単に記述できるようにするために、いくつかの言語が設計されています。例には、次の言語が含まれます。

多くのUnixユーティリティは単純な文字列操作を実行し、いくつかの強力な文字列処理アルゴリズムを簡単にプログラムするために使用できます。ファイルと有限ストリームは文字列として表示される場合があります。

マルチメディア制御インターフェース埋め込みSQLprintfなどの一部のAPIは、文字列を使用して、解釈されるコマンドを保持します。

Perl、Python、Ruby、Tclなどの最近のスクリプトプログラミング言語は、テキスト操作を容易にするために正規表現を採用しています。Perlは、その正規表現の使用で特に注目されており[10]、他の多くの言語やアプリケーションは、Perl互換の正規表現を実装しています。

PerlやRubyなどの一部の言語は、文字列補間をサポートしています。これにより、任意の式を評価して文字列リテラルに含めることができます。

文字列関数

文字列関数は、文字列を作成したり、可変文字列の内容を変更したりするために使用されます。また、文字列に関する情報を照会するためにも使用されます。関数のセットとその名前は、コンピュータープログラミング言語によって異なります

文字列関数の最も基本的な例は、文字列の長さ関数です。これは、文字列の長さを返し(ターミネータ文字や文字列の内部構造情報をカウントしない)、文字列を変更しない関数です。この関数は、多くの場合、lengthまたはと呼ばれlenます。たとえば、length("hello world")11を返します。別の一般的な関数は連結です。この場合、2つの文字列を追加することによって新しい文字列が作成されます。多くの場合、これは+加算演算子です。

一部のマイクロプロセッサ命令セットアーキテクチャには、ブロックコピー(例: Intel x86m )などの文字列操作の直接サポートが含まれていますREPNZ MOVSB[11]

正式な理論

Σをアルファベットと呼ばれる有限の記号セット(別名文字)とします。シンボルの性質については何も想定されていません。Σ上の文字列(または単語)は、Σからの任意の有限の記号シーケンスです。[12]たとえば、Σ= {0、1}の場合、01011はΣ上の文字列です。

文字列長さsは、 s内のシンボルの数(シーケンスの長さ)であり、任意の非負の整数にすることができます。多くの場合、|と表されます。s |。の文字列は、長さ0のΣ上の一意の文字列であり、εまたはλで表されます。[12] [13]

長さnのΣ上のすべての文字列のセットはΣnで表されます。たとえば、Σ= {0、1}の場合、Σ2 = {00、01、10、11}です。任意のアルファベットΣに対してΣ0 = {ε}で あることに注意してください。

任意の長さのΣ上のすべての文字列のセットは、Σのクリーネ閉包であり、Σ *で表されます。Σnに関しては

たとえば、Σ= {0、1}の場合、Σ * = {ε、0、1、00、01、10、11、000、001、010、011、...}。集合Σ *自体は可算無限ですが、Σ *の各要素は有限長の文字列です。

Σ上の文字列のセット(つまり、Σ *のサブセット)は、Σ上の形式言語と呼ばれます。たとえば、Σ= {0、1}の場合、偶数のゼロを持つ文字列のセット{ε、1、00、11、001、010、100、111、0000、0011、0101、0110、1001、 1010、1100、1111、...}は、Σの形式言語です。

連結と部分文字列

連結はΣ *の重要な二項演算です。Σ *の任意の2つの文字列stの場合、それらの連結は、 sの記号のシーケンスとそれに続くtの文字のシーケンスとして定義され、 stで表されます。たとえば、Σ= {a、b、...、z}、 s  = 、およびt  = の場合、 st  = およびts  = bearhugbearhughugbear

文字列の連結は結合法則です可換ではありません。空の文字列εは単位元として機能します。任意の文字列sに対して、εs = = sしたがって、集合Σ *と連結演算は、Σによって生成される自由モノイドであるモノイドを形成します。さらに、長さ関数は、Σ *から非負の整数までのモノイド準同型を定義します(つまり、関数、 そのような)。

文字列sは、 t = usvのような(空の可能性がある)文字列uおよびvが存在する場合、部分文字列またはtの因数あると言われます「の部分文字列です」という関係、 Σ *の半順序を定義し、その最小要素は空の文字列です。

プレフィックスとサフィックス

文字列sは、 t = suのような文字列uが存在する場合tの接頭辞であると言われますuが空でない場合、 sはtの適切な接頭辞であると言われます対称的に、t = usのような文字列uが存在する場合、文字列sはtの接尾辞あると言われますuが空でない場合、 sはtの適切な接尾辞であると言われます接尾辞と接頭辞はtの部分文字列です。「の接頭辞である」と「の接尾辞である」の関係は両方とも接頭辞の順序です。

逆転

文字列の逆は、同じ記号で逆の順序の文字列です。たとえば、s = abc(a、b、およびcはアルファベットの記号)の場合、sの逆はcbaです。それ自体の逆の文字列(たとえば、s = madam)は回文と呼ばれ、空の文字列と長さ1のすべての文字列も含まれます。

ローテーション

文字列s = uvは、 t = vuの場合、tの回転であると言われますたとえば、Σ= {0、1}の場合、文字列0011001は0100110の回転であり、u = 00110およびv = 01です。別の例として、文字列abcには3つの異なる回転があります。abc自体(u = abc、v =ε)、bca(u = bc、v = a)、およびcab(u = c、v = ab)。

辞書式順序

文字列のセットに順序を定義すると便利なことがよくあります。アルファベットΣに全順序がある場合(アルファベット順を参照)、辞書式順序と呼ばれるΣ *で全順序を定義できます。たとえば、Σ= {0、1}および0 <1の場合、Σ *の辞書式順序には、関係ε<0 <00 <000 <... <0001 <001 <01 <010 <011 <0110 <が含まれます。 01111 <1 <10 <100 <101 <111 <1111 <11111 ...辞書式順序は、アルファベット順がそうである場合は合計ですが、アルファベット順がそうである場合でも、重要なアルファベットについては十分に根拠がありません

十分な根拠を維持する代替の文字列の順序については、 Shortlexを参照してください。

文字列操作

文字列に対するいくつかの追加の操作は、通常、形式理論で発生します。これらは、文字列操作に関する記事に記載されています。

トポロジー

長さ3のバイナリ文字列の(ハイパー)キューブ

文字列は、グラフ上のノードとして次の解釈を認めます。ここで、kはΣのシンボルの数です。

固定長ストリングまたは可変長ストリングのセットの自然トポロジーは離散トポロジーですが、無限ストリングのセットの自然トポロジーは限界トポロジーであり、無限ストリングのセットをのセットの逆限界と見なします。有限の文字列。これは、p進数とカントール集合のいくつかの構造に使用される構造であり、同じトポロジーを生成します。

トポロジの文字列表現間の同型は、字句的に最小の文字列回転に従って正規化することで見つけることができます

も参照してください

参考文献

  1. ^ 「Javaの紹介-MFC158G」2016-03-03にオリジナルからアーカイブされました。文字列リテラル(または定数)は「匿名文字列」と呼ばれます
  2. ^ ブライアント、ランダルE .; David、O'Hallaron(2003)、Computer Systems:A Programmer's Perspective(2003 ed。)、Upper Saddle River、NJ:Pearson Education、p。40、ISBN  0-13-034074-X2007年8月6日にオリジナルからアーカイブ
  3. ^ ウェアマウス、ジェフ。「SinclairZX80のROMのアセンブリリスト」2015年8月15日にオリジナルからアーカイブされました。{{cite web}}:CS1 maint:不適切なURL(リンク
  4. ^ アリソン、デニス。「TinyBASICのデザインノート」2017年4月10日にオリジナルからアーカイブされました。
  5. ^ チャールズクロウリー。 「テキストシーケンスのデータ構造」 は、WaybackMachineで2016年3月4日にアーカイブされました。ウェイバックマシンで2016年4月4日にアーカイブされたセクション 「はじめ に」 。
  6. ^ 「strlcpyとstrlcat-一貫性があり、安全で、文字列のコピーと連結。」ウェイバックマシンで2016年3
  7. ^ 「strcpy、strncpy、strlcpyについての暴言。」ウェイバックマシンで2016-02-29
  8. ^ キーストンプソン。「いいえ、strncpy()は「より安全な」strcpy()ではありません」。2012年。
  9. ^ 「プラハストリングロジークラブ」stringology.org2015年6月1日にオリジナルからアーカイブされました2015年5月23日取得
  10. ^ 「エッセンシャルPerl」2012年4月21日にオリジナルからアーカイブされました。Perlの最も有名な強みは、正規表現を使用した文字列操作にあります。
  11. ^ 「x86文字列命令」2015-03-27にオリジナルからアーカイブされました。
  12. ^ a b Barbara H. Partee; アリス・テル・メーレン; ロバートE.ウォール(1990)。言語学における数学的方法クルーワー。
  13. ^ ジョン・E・ホップクロフト、ジェフリー・D・ウルマン(1979)。オートマトン理論、言語、および計算の概要アディソン-ウェスリー。ISBN 0-201-02988-Xここで:sect.1.1、p.1