무어 기계

무어 기계(Moore machine)는 현재 상태에 따라 출력이 결정되는 유한 상태 기계이다. 이름은 미국의 수학자이자 컴퓨터 과학자인 Edward F. Moore에서 따왔다. 무어 기계의 상태 전이는 입력에 의해 정해진다. 예를 들어 입력이 aabba이면 어떤 무어 기계는 PRETTY를 출력할 수 있다.

상태는 노드로, 전이는 입력 심볼이 붙은 화살표로 나타낸다. 상태 중 하나가 시작 상태이며, 상태 N과 그 출력 심볼 S를 함께 N/S로 표기한다.

일반적으로 무어 기계는 사이클을 가질 수 있지만, 이 문제에서는 사이클이 전혀 없는 무어 기계만 다룬다. 이런 기계를 직병렬 무어 기계라고 부른다.

직병렬 무어 기계는 다음과 같이 문자열로 간단히 표현할 수 있다.

• 상태가 하나이고 출력이 S인 기계는 S로 쓴다. (S는 알파벳 대문자)
• 상태가 하나이고 출력 심볼이 지워진 기계는 _로 쓴다.
• 부분 기계 M1, M2, …, Mk를 직렬로 연결한 기계는 M1M2…Mk로 쓴다.
• 부분 기계를 병렬로 연결한 기계는 M1|M2|…|Mk로 쓴다.
• 어떤 기계가 더 큰 기계의 일부로 쓰이면 그 부분을 괄호로 감싼다.

직렬로 연결된 기계의 출력은 각 부분 기계의 출력을 순서대로 이어 붙인 것이다. 병렬로 연결된 기계의 출력은 여러 갈래 중 정확히 하나의 부분 기계가 내는 출력이다.

이 직병렬 무어 기계에서 출력 심볼 하나가 지워졌다(_로 표시). 기계의 표현식과 실제로 관측된 출력 문자열이 주어질 때, 지워진 심볼이 무엇인지 알아내는 프로그램을 작성하시오.

예를 들어 기계가 A(B|_)C이고 출력이 ADC이면, 가운데 병렬부에서 B가 아니라 지워진 상태를 지난 것이므로 지워진 심볼은 D이다. 만약 기계가 A(B|D|_)C이고 출력이 ADC이면, 가운데 글자 D가 D 갈래에서 나온 것인지 지워진 갈래에서 나온 것인지 구별할 수 없으므로 지워진 심볼을 유일하게 결정할 수 없다. 또한 관측된 출력이 그 기계가 절대로 만들 수 없는 문자열일 수도 있다.

따라서 지워진 심볼을 유일하게 결정할 수 있으면 그 심볼을, 유일하게 결정할 수 없으면 _를, 주어진 기계가 그 출력을 만들 수 없으면 !를 출력한다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 직병렬 무어 기계의 표현식이, 둘째 줄에는 관측된 출력 문자열이 주어진다. 출력 심볼은 모두 알파벳 대문자이다. 기계의 가장 바깥쪽 연결은 항상 직렬이며, 지워진 심볼(_)은 정확히 하나이다. 각 줄의 길이는 100 이하이다.

각 테스트 케이스마다 한 줄에 답을 출력한다. 지워진 심볼을 유일하게 결정할 수 있으면 그 심볼을 출력한다. 유일하게 결정할 수 없으면 _를 출력한다. 주어진 기계가 관측된 출력을 만들 수 없으면 !를 출력한다.