다음 문법으로 생성되지 않는 문장은?<S> ::= 1<… | [7급 국가직 프로그래밍언어론] 08년 1회차 기출문제 상세 페이지
1[7급 국가직 프로그래밍언어론] 08년 1회차
다음 문법으로 생성되지 않는 문장은?<S> ::= 1<A> | 0<B>
<A> ::= 0<A> | 1<B>
<B> ::= 1<B> | 0
1
0110
2
1110
3
01100
4
100110
해설
생성되지 않는 문장은 01100이다.
<B> 는 1을 0개 이상 반복한 뒤 0 하나로 끝나는 문자열만 만든다. 0으로 시작하면 S → 0<B> 이므로 나머지가 1…10 꼴이어야 하는데, 1100 은 0이 두 개라 <B> 로 만들 수 없다.
- 0110 은 0 뒤에 <B> 가 110 을 만들어 생성된다.
- 1110 은 1 뒤에 <A> → 1<B>, <B> 가 10 을 만들어 생성된다.
- 100110 은 1 뒤에 <A> 가 0을 두 번 붙이고 1<B> 로 넘어가 <B> 가 10 을 만들어 생성된다.
오류나 개정된 내용이 보이면 알려주세요