언어 방정식

언어 방정식은 숫자 방정식을 닮은 수학적 문장이지만, 변수는 숫자보다는 형식 언어의 값을 가정한다.숫자 방정식의 산술 연산 대신, 변수는 언어 연산에 의해 결합된다.A와 B 두 언어에서 가장 일반적인 작업으로는 집합 조합 A ∪ B, 집합 교차로 A ∩ B, 결합 A ⋅B가 있다.마지막으로, 단일 피연산자를 취하는 작업으로서, 세트 A는^* 언어 A의 클레인 별을 가리킨다.그러므로 언어 방정식은 문법에 의해 생성된 언어가 언어 방정식의 시스템의 해결책이 되어야 하기 때문에 공식 문법을 나타내는 데 사용될 수 있다.

언어 방정식 및 문맥 없는 문법

긴즈버그와 라이스는^[1] 언어 방정식에 의한 문맥 없는 문법에 대한 대체 정의를 내렸다.To every context-free grammar ${\displaystyle G=(V,\Sigma ,R,S)}$, is associated a system of equations in variables ${\displaystyle V}$. Each variable ${\displaystyle X\in V}$ is an unknown language over ${\displaystyle \Sigma }$ and is defined by the equation ${\displaystyle X={\alpha }_1\cup \dots \cup {\alpha }_m}$${\displaystyle X=\alpha _{1}\cup \ldots \cup \alpha _{m}}$ where ${\displaystyle X\to \alpha _{1}}$, ..., ${\displaystyle X\to \alpha _{m}}$ are all productions for ${\displaystyle X}$. Ginsburg and Rice used a fixed-point iteration argument to show that a solution always exists, and proved that the assignment $X{\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle G_{}}$( ${\displaystyle X}$) ${\displaystyle X=L_{G}(X)}$는 이 시스템에 대한 최소 솔루션이며,^[clarify] 즉 다른 솔루션은 이 시스템의 하위^[clarify] 집합이어야 한다.

For example, the grammar ${\displaystyle S\to aSc\mid b\mid S}$ corresponds to the equation system ${\displaystyle S=(\{a\}\cdot S\cdot \{c\})\cup \{b\}\cup S}$ which has as solution every superset of ${\displaystyle \{a^{n}bc^{n}\mid n\in {\$$mathcal {{N$

교차점이 추가된 언어 방정식은 접속 문법에 유사하게 대응한다.^{[citation needed]}

언어 방정식과 유한 자동식

모든 연결 왼쪽에 있으면 singleton상수 언어를 있Brzozowski과 Leiss[2]. 변수 X{X\displaystyle}을 X⋅ Y{\displaystyle X\cdot Y}도 X{를}{\displaystyle X\cdot){a\}⋅}. 각각의 방정식이 남아 있다며 언어 방정식{를}⋅ X{\displaystyle\와 같이{a\}\cdot X}를 공부했다.항의라도rm $X{\displaystyle {}_{}}$ ${\displaystyle i_{}}$= ${\displaystyle F(}$ ${\displaystyle {X\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle }$.${\displaystyle }$. . . ${\displaystyle X_{}}$k )$${\$displaystyle X_{i}=F(X_{1$}, $..., X_{k})$ 오른쪽에 변수가 하나 있는$$ 경우.모든 비계수적 유한 자동화는 좌-정합성과 결합을 사용한 그러한 방정식을 가지고 있다. 그림 1. 교차 연산이 허용되는 경우 방정식은 유한한 자동자를 교대하는 것에 해당한다.

Baader and Narendran^[3] studied equations ${\displaystyle F(X_{1},\ldots ,X_{k})=G(X_{1},\ldots ,X_{k})}$ using left-concatenation and union and proved that their satisfiability problem is EXPTIME-complete.

콘웨이 문제

Conway는^[4] 다음과 같은 문제를 제안했다: 일정한 유한 $언어{\displaystyle }$ L ${\displaystyle$ L$}$을$($를) 주어진다면 $L{\displaystyle }$ ${\displaystyle X}$= ${\displaystyle X}$ ${\displaystyle L}$ ${\displaystyle LX=XL}$ 방정식의 가장 큰 해결책은 항상$$ 규칙적인가?이 문제는 카루메키와 페트레에^[5][6] 의해 연구되었는데, 그는 특별한 경우에 긍정적인 대답을 했다.콘웨이의 문제에 대해 이 방정식의 최대 해법이 반복적으로 열거되지 않도록 유한한$$ 언어 $[\$디스플레이 $스타일 L}$을(를) 구축한 쿤크가^[7] 강하게 부정적으로 대답했다.

쿤크는^[8] 또한 불평등 $L{\displaystyle }$ ${\displaystyle X}$ ${\displaystyle \subseteq }$ X ${\displaystyle L}$ ${\displaystyle LX\subseteq XL}$의 가장 큰 해결책은 항상 규칙적이라는$$ 것을 증명했다.

부울 연산이 있는 언어 방정식

결합과 부울 연산을 포함한 언어 방정식은 주어진 방정식에 대한 만족도 문제가 불문율이며, 언어 방정식의 시스템이 고유한 해결책을 가지고 있다면 그 해결책은 재귀적이라는 것을 입증한 Parikh, Chandra, Halpern, Meyer에 의해 처음 연구되었다.나중에 옥호틴은^[10] 불만족성 문제가 RE-완전성이며 모든 재귀언어가 어떤 방정식의 고유한 해결책임을 증명했다.

단항 알파벳에 대한 언어 방정식

한 글자의 알파벳으로, 리스는^[11] 보완과 결합 연산을 이용하여 비정규 해법이 있는 제1언어 방정식을 발견했다.후에 제는^[12] 비정규적인 단항어는 결합, 교차로, 결합으로 이루어진 언어 방정식으로 정의될 수 있다는 것을 보여주었는데, 이는 결합 문자에 해당한다.이 방법에 의해 제이와^[13] 옥호틴은 모든 재귀적인 단항어가 어떤 방정식의 독특한 해법이라는 것을 증명했다.

참고 항목

• 부울 문법
• 아르덴의 법칙
• 제약 조건 설정

참조

외부 링크

• 언어 방정식의 이론 및 적용에 관한 워크숍 (TALE 2007)