정규 표현식

Question

우선 내가 물어 보는 것에 대한 올바른 번역인지 여부는 알 수 없습니다.

내 수업 중 하나에서 우리는 정규식, 공식 언어 등에 대해 배우는 것을 봤습니다.

Alphabet {1,0,S,R} 
Terminals {1,0} 
Rules: 

S ::= 0 
S ::= 1 
S ::= 1R 
R ::= 1R 
R ::= 0R 
R ::= 1 
R ::= 0 

이 경우에는 1R로 시작한다고 가정하면 1R 또는 0R로 계속 진행할 수 있습니다.

1R로 시작하면 1 ... 다음 문장 (이 경우 해당 이진수)이 올바르게 완료 되었습니까? 이후에 "추가"할 수 없기 때문에 1R이라고 말하면 1을 선택한 다음 다시 1R을 선택합니까?

미리 감사 드리며, 틀린 경우 다시 게시/이동하십시오.

---

ADDED :

0 at rule S ::= 0 
1 with S ::= 1 
10 with S ::= 1R, so R ::= 0 

어떻게 1,100,110를 생성?

이것은 숙제가 아니며 파워 포인트의 예제/질문입니다. 나는 그것이 어떻게 행해지는지 알지 못한다.

Answer 1

정규식은 문맥 자유형 문법을 사용하여 정의 된 정규 언어입니다. 동일한 언어를 정의하는 정규 표현식은 (0)U(1{0,1}*)입니다. 보통 영어로 일반 언어는 0과 1의 모든 문자열과 1로 시작하는 문자열을 포함합니다.

문맥 자유 문법은 일부 초기 비가 입자 기호로 시작합니다.이 경우에는 S로 나타납니다. 그런 다음 나열된 생산 규칙에 따라 비단 호 기호를 기호 열로 대체 할 수 있습니다. 문자열에 비 - 터미널 기호가 포함되어 있지 않으면 "완료"됩니다.

대체 할 문자열에 현재 S 또는 R이 있으면 "1R"만 선택할 수 있습니다. 이 문법에 따라 R을 1로 처음 바꾸면 더 이상 대체 할 터미널이 없기 때문에 문자열 생성이 완료됩니다.

편집 : 여기에 1100110.

S 
1R   via S ::= 1R 
11R  via R ::= 1R 
110R  via R ::= 0R 
1100R  via R ::= 0R 
11001R  via R ::= 1R 
110011R via R ::= 1R 
1100110 via R ::= 0 

Answer 2

정확합니다. 추가는 허용되지 않으며 대체 만 허용됩니다. 그러나이 언어를 사용하면 "R :: = 1R"또는 "R :: = 0R"을 선택한 다음 R을 다시 한 번 대체하여 문자열을 계속 길게 만들 수 있습니다.

Answer 3

1R로 시작하면 1 ... 다음 문장 (이 경우 해당 이진수)이 올바르게 완료 되었습니까?

네, 맞습니다. 문장 11은 S = 1R = 11과 일치합니다.

그러나이 문법을 사용하면 문장에 더 많은 자릿수를 추가 할 때 항상 R = 1R 또는 R = 0R을 사용할 수 있습니다.

편집 : 질문 편집 질문에 답변

어떻게 1,100,110를 생성? 당신이 이해하는 데 도움이

1100110 = S = 1R = 11R = 110R = 1100R = 11001R = 110011R = 1100110

희망.

행운을 빌어 요!