a(a|b)*a로 나타낼 수 있다. 이를 상태도로 표시하면
모든 NFA 는 DFA 로 변경이 가능하다. 위 보기에서 예를 들면 위에서 q1 상태에서 입력 기호 a 가 온다면 q1,q2 상태로 갈수 있으므로 이를하나의 상태로 묶고 , q1,q2 상태에서 입력 심볼에서 갈수 있는 상태를 각각 생각하면
일반적으로 잠수함 엔진이 작동할 때에 나오는 소리는 잠수함 종류에 따라서 다르다고 한다. 우리는 물 속에서 들리는 소리의 패턴을 듣고서 그 소리가 특정한 잠수함에서 나오는 소리인지 아닌지를 알아내려고 한다.이 문제에서는 잠수함의 소리가 두 종류의 단위소리의 연속으로 이루어져 있고,그 단위 소리를 각각 0 과 1 로 표시한다.
또, 한 특정한 소리의 반복은 ~ 로 표시한다. 예를 들어 X~ 는 X 과 한 번 이상 반복되는 모든 소리의 집합을 말하고,(xyz)~ 는 괄호안에 있는 xyz 로 표현된 소리가 한 번이상 반복되는 모든 소리의 집합을 말한다. 다음의 예를 보라.
1~ = {1,11,111,....}
(01)~ = {01,0101,010101,....}
(1001)~ = {10001,10011001,100110011001,....}
10~11 = {1011,10011,100011,....}
(10~1)~ = {101,1001,100001,101101,....}
그리고 (x | y) 는 x 또는 y 중에서 아무거나 하나 만을 선택해서 만든 소리의 집합, 즉 집합 {x,y} 를 의미한다. 예를 들면 (1001 | 0101) 은 집합 {1001,0101}을 의미한다. 따라서 (0 | 1)~ 은 0 과 1 로 이루어진 모든 스트링의 집합, 즉 모든 소리의 집합을 말한다.
또 한 예를 보면 (100 | 11)~ 은 100 과 11 을 마음대로 섞어서 만들 수 있는 모든 소리의 집합을 의미한다. 즉 (100 | 11)~ 에 해당하는 스트링을 집합으로 나타내면 {100,11,10011,11100,100100100,1110011,....} 이 된다.
우리가 식별하고자 하는 잠수함의 엔진소리의 패턴은 다음과 같다.
(100~1~ | 01)~
여기에 속하는 소리의 예를 들어보면 1001,01,100001,010101,10000011110101,1001110101 ,.... 이다. 다시 말해서 이것은 100~1~ 과 01 을 임의로 섞어서 만들 수 있는 모든 스트링의 집합을 나타낸다.
입력으로 0 과 1 로 구성된 스트링이 주어 질때, 이 스트링이 앞에서 기술된 잠수함의 엔진소리인지 아닌지를 판별하는 프로그램을 작성하라. 실행파일의 이름은 sub.exe 로 한다.
10010111 noise 01001011000001 noise 100000000000101 submarine 11111110000 noise 10000001111110101100111101 submarine
출처:한국 정보올림피아드 중고등부 기출
(풀이) NFA 를 DFA 로 변경하는 문제이다.
0 이 입력되는 경우
1 이 입력되는 경우
0 이 입력되는 경우
1 이 입력되는 경우
이렇게 번호를 부여할 경우 4,5,8 번 상태가 종료 상태 즉 4 , 5 , 8 번 상태에서 종료하면 이 신호는 잠수함 신호이다.
(유제) 00(1|0)*11+ 을 인식하는 문자열이면 O 를 아니면 X 를 출력하는 프로그램을 작성하라.
| 는 or 을 의미하고 * 는 0 번 이상 + 는 1 번 이상의 문자(열)이 반복될수 있다는 의미이다.
입력 파일 input.txt 에는 0 과 1 로 구성된 스트링이 1 개 들어있다. 이 때 스트링의 길이는 200 개 이하로 제한한다.
입력 파일에 있는 스트링을 읽고, 가능하면 O 를 아니면 X 를 출력하라.
입력(input.txt) 001011 0011 00101 출력(화면) O O X