다음의 언어 L을 생성하는 문법으로 옳은 것은? (단, 언어 L의 알파… | [7급 국가직 프로그래밍언어론] 11년 1회차 기출문제 상세 페이지
1[7급 국가직 프로그래밍언어론] 11년 1회차
다음의 언어 L을 생성하는 문법으로 옳은 것은? (단, 언어 L의 알파벳은 {a, b, c}이다)1
S → aA
A → aA | B
B → Bb | c
2
S → aAb
A → c
3
S → aAb
A → aAb | c
4
S → aSb | c
해설
옳은 문법은 S → aSb | c이다. 재귀 규칙이 a 와 b 를 같은 개수로 짝지어 감싸고, n = 0 이면 c 만 생성된다.
S → aSb 를 n번 적용한 뒤 S → c 로 끝내면 이 정확히 만들어진다.
- S → aA, A → aA | B, B → Bb | c 는 a 의 개수와 b 의 개수를 서로 독립적으로 늘려 개수를 맞추지 못하며 c 단독도 만들 수 없다.
- S → aAb, A → c 는 acb 한 문자열만 생성한다.
- S → aAb, A → aAb | c 는 a 와 b 가 최소 하나씩 있어야 하므로 n = 0 인 c 를 생성하지 못한다.
오류나 개정된 내용이 보이면 알려주세요