1
L = {W (WR) *}, w = (a + b) * WR은 W의 반대입니다. 이 언어는 정규입니까?W (WR) * 정기?
나는 정기적으로 읽지 않아도되는 W (WR)을 가질 수있는 경우가 있기 때문에 정기적으로 읽지 말아야하지만 책에는 대답이 규칙적이어야합니다.
누구든지 설명 할 수 있습니까?
A
답변
1
트릭이 별입니다. (WR) *에는 빈 단어가 포함됩니다. 따라서, L은 빈 단어, 즉 모든 단어 W와 연결되는 모든 단어 W를 포함하며, 모든 단어 세트는 물론 규칙적이다.
W (WR)^+의 경우 상당히 달라 보입니다. 그러나 스타와 함께 모든 반전은 언어의 여러 단어 중 일부일뿐입니다.
W (WR)^+는 어떤 언어 범주에 해당합니까? @Peter Leupold – Zephyr
W (WR)^+는 컨텍스트 프리가 아니지만 (펌프 보조 정리 참조) 상황에 따라 다릅니다. 짝수 길이의 문장의 언어 인 W (WR)을 사용하는 경우, 이것은 규칙적이 아니고 선형 적이기 때문에 문맥이 없습니다. @ 자일 렌 23 –