矩陣文法-句耩式圖型別之研究

Abstract

在構造圖型識別的研究之中，正規語言是一個極為重要的工具。正規語言中“文法” 產生“語言”的觀念被應用。因此構造圖型識別的研究，希望把圖型的資訊化成能用 文法生成的字串形態，然後便可利用文法及其相對的自動機，對化成的字串作生成或 接受的處理。故圖型可以用簡單的文法來表示，并且圖型可被不同的文法所分類，達 到辨認的效果。 但是圖型的資訊有時難以變換成字串的形態，這時就需要發展高維的圖型文法以及相 對應的接受機，直接對圖型作處理，在以過二十年間有樹狀文法(tree grammar), 陣 列文法(array grammar),圖文法(graph grammar) 等圖型文法的研究, 并有對矩陣文 法(matrix grammar)的基本定義, 但對矩陣文法的研究并不多。矩陣文法的結構有些 類似樹狀文法及陣列文法, 但是矩陣文法是一個組合文法, 有平形處理的好處；且一 般化的矩陣文法定義，可使得矩陣語言函括範圍深廣。本篇主旨就是對矩陣文法應用 在構造圖型識別的問題上加以研究。 在本篇中，矩陣文法及語言被定義且發展於二維點矩陣圖型的表示。雜訊矩陣圖型的 校正問題被考慮且發展出校正的演算法。由樣本矩陣所推導的矩陣文法亦被定義。