언어의 크기

(형식) 언어(language)는 문자열의 집합이다. 특정 언어를 나타내는 한 가지 방법은 보통의 집합 표기법을 쓰는 것이지만, 집합이 큰 경우에는 문법(grammar)으로 표현하는 편이 더 편리할 수 있다.

여기서 다루는 문법은 두 부분으로 이루어진다.

• 시작 문자열(initial string) 하나
• s1 -> s2 꼴의 치환 규칙들의 집합 (여기서 s1, s2는 문자열이다)

이 문법이 정의하는 언어는, 시작 문자열에서 출발하여 현재 문자열 안에 나타나는 s1을 s2로 바꾸는 치환을 원하는 만큼 반복해 만들 수 있는 모든 문자열의 집합이다. 치환을 한 번도 적용하지 않은 결과, 즉 시작 문자열 자체도 언어에 포함된다.

예를 들어, 시작 문자열이

"AyB"

이고 치환 규칙이

{ "A" -> "ab", "Ay" -> "cdy", "B" -> "w", "B" -> "x" }

인 문법 G를 생각하자. 이 G가 생성하는 언어는 다음과 같다.

L = { "AyB", "Ayw", "Ayx", "abyB", "abyw", "abyx", "cdyB", "cdyw", "cdyx" }

문법 G가 주어질 때, 그 문법이 생성하는 언어에 서로 다른 문자열이 몇 개 들어 있는지 구하여라.

첫째 줄에는 시작 문자열이 주어진다.

그 다음 줄부터는 치환 규칙이 한 줄에 하나씩 파일의 끝까지 주어진다. 치환 규칙은 최대 100개이다. 입력에 등장하는 각 문자열은 0개에서 10개 사이의 알파벳 대소문자로 이루어지며, 큰따옴표로 둘러싸여 있다. 입력에는 공백이 없다.

문법 G가 생성하는 언어에 들어 있는 서로 다른 문자열의 개수를 정수 하나로 출력한다. 서로 다른 문자열이 1000개보다 많으면, 그 개수 대신 Too many.를 출력한다.