문법 G가 다음과 같을 때 S1으로부터 생성할 수 없는 것은?G : S… | [9급 지방직 컴퓨터일반] 15년 1회차 기출문제 상세 페이지
1[9급 지방직 컴퓨터일반] 15년 1회차
문법 G가 다음과 같을 때 S1으로부터 생성할 수 없는 것은?
- G : S1 → 0S2 S1 → 0
- S2 → 0S2 S2 → 1
1
0
2
00
3
01
4
001
해설
시작 기호 S1에서 생성할 수 없는 문자열은 00이다.
S1은 0으로 끝나거나 0S2로 바뀌고, S2는 0을 몇 개 붙인 뒤 반드시 1로 끝난다. 따라서 생성되는 문자열은 0 하나이거나 0 뒤에 0이 여러 개 이어지고 1로 끝나는 형태뿐이다.
- 0은 S1 → 0 규칙 하나로 바로 생성된다.
- 01은 S1 → 0S2 → 01로 생성된다.
- 001은 S1 → 0S2 → 00S2 → 001로 생성된다.
00은 길이가 2 이상인데 1로 끝나지 않으므로 어떤 유도로도 만들 수 없다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.