制限された消去オートマトン

阿江 忠  大崎 重義  

誌名
電子情報通信学会論文誌 D   Vol.J61-D   No.7   pp.504-511
発行日: 1978/07/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(630.2KB)>>
論文を購入




あらまし: 
有限オートマトンを若干拡張したオートマトンとして,入力テープ上の文字を読んだときはその文字を空白記号に書換える(これを消去するという)オートマトンを新たに提案した.このオートマトンを消去オートマトンと呼ぶが,本論文では特に,入力テープ上の非空白文字の系列はどの時点でも連結性を保つような読み方をする部分クラスの性質を明らかにした.このような消去オートマトンをEACと略記するが,EACの受理する言語のクラスは線形言語のクラスと一致し,同じオートマトンの決定性のタイプDEACの受理する言語のクラスは文献(4)の単純線形言語のクラスと一致することが示される.その結果,文献(4)で未解決であった若干の言語の性質も明らかになる.更に,従来のオートマトンモデルとの関連についても議論されている.