| 引用本文: | 王兵山,肖计田,黄晓秋.线性语言和顺序语言关于置换的判定问题.[J].国防科技大学学报,1983,(4):83-87.[点击复制] |
| Wang Bingshan,Xiao Jitian,Huang Xiaoqiu.Some Decisoin Problems in a Linear Languages and Sequential Languages for a Substitution[J].Journal of National University of Defense Technology,1983,(4):83-87[点击复制] |
|
| |
|
|
| 本文已被：浏览 4999次 下载 5223次 |
| 线性语言和顺序语言关于置换的判定问题 |
| 王兵山, 肖计田, 黄晓秋 |
|
()
|
| 摘要: |
| S.Ginsburg 和 G.F.Rose 在[1]中利用可定义集合及顺序可定义集合的概念，得到了cfl（上下文无关语言)和sl(顺序语言)关于gsm(广义顺序机)和csm(完全顺序机)的判定问题之不可解性。本文用更初等的方法，不仅得到了11和sl关于gsm和csm的判定问题之不可解性，而且还得到了ll( 线性语言)和sl关于置换和同态的判定问题之不可解性，顺便还得到了11和s1关于补运算的不封闭性。
我们首先引进一些概念和记号。注意，凡是文中没有说明的概念和符号，都可以在[1]和[3]中找到。 |
| 关键词: |
| DOI： |
| 投稿日期：1983-01-12 |
| 基金项目: |
|
| Some Decisoin Problems in a Linear Languages and Sequential Languages for a Substitution |
| Wang Bingshan, Xiao Jitian, Huang Xiaoqiu |
| Abstract: |
| In this paper，we examined the decision problems in a linear languages (for short LL) and Sequential languages (for short SL) for a Substitution. Following results are proved：
Theorem 3 The problems of determining of given LL's (or SL's) L1 and L2 whefher or not there exists a substitution f mapping regular sets into regular sets is undecidable.
Corollary 4 They are all undecidable to determine of arbitrary LL's (or SL's) L1 and L2 whether or not a f so that f(L1)=L2，where i) f is a homomorphism，or
ii) f is a substitution，or
iii)f is a ε-free substitution，or
iv) f is a k-limited erasing substitution，or
v) f is a generalized sequential machine，or
vi) f is a complete sequential machine. |
| Keywords: |
|
|
|
|
|
