0
내가 성명, " CFG는 정기적 인 언어를 만들 수 있습니다"또는 모든 CFG 모두 (모든) 정규 언어
A
답변
0
나는 이것이 더 생각을 만들 수 있어야한다 우연히 어디 현재 계산의 이론을 공부하고
언어 문제는 컴퓨터 과학 문제입니다. 즉, 여기에 내가 전달하려고하는 것의 더 명확한 공식이 될 수 있습니다 :
일반 언어의 경우 해당 일반 언어를 생성하는 컨텍스트없는 문법이 있습니다.
이것을 보려면 표준 언어에 대한 표준 문맥 자유 문법을 먼저 만들 수 있습니다. 우리는 RL에 대한 표준 CFG로서 오른쪽 규칙 문법을 택할 수 있습니다. 나는 그 구조에 대한 세부 사항을 설명하지는 않겠지 만, 언어에 대한 DFA가 알려져 있고 생산이 오토 마톤에서 전환을 반영하는 CFG를 생성한다고 가정합니다.
RL에 대한 단일 CFG의 존재를 감안할 때, 우리는 즉시 임의의 RL에 대해 동등한 많은 CFG가 있다는 것을 알게됩니다.
0
실제로 REG는 CF의 하위 집합입니다. 따라서 모든 정규 언어는 문맥이 없으며 CFG에서 생성 할 수 있습니다.