다음의 언어 L을 생성하는 문법으로 옳은 것은? (단, 언어 L의 알파… | [7급 국가직 프로그래밍언어론] 11년 1회차 기출문제 상세 페이지

1[7급 국가직 프로그래밍언어론] 11년 1회차
다음의 언어 L을 생성하는 문법으로 옳은 것은? (단, 언어 L의 알파벳은 {a, b, c}이다)
L={ ancbn∣n≥0 }L = \{\ a^{n}cb^{n} \mid n \geq 0\ \}
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 로 끝내면 ancbna^{n}cb^{n} 이 정확히 만들어진다.

  • 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 를 생성하지 못한다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 프로그래밍언어론] 11년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 프로그래밍언어론 기출문제 암기장 전체 보기