컴파일러 정규표현에서 NFA로 변환
S -> 0A
A -> 1S | 1일때입니다
표현식은 쉽게 구했는데 NFA로 변환하는 법이 헷갈립니다 대거 있는 걸로 하는 게 좋을지
제가 한 것 중에 혹시 틀린 게 있다면 피드백 부탁드립니다
안녕하세요.
질문 주신 식 S → 0A, A → 1S | 1 은 결과적으로 정규식 (01)+ 형태로 변환됩니다.
작성하신 NFA 그림도 전반적인 방향은 맞지만, ε(엡실론) 전이와 상태 수가 불필요하게 많습니다.
아래처럼 정리하면 훨씬 깔끔하고 정확합니다.
1. 핵심 구조 요약
(01)+ 는 “01”이 한 번 이상 반복되는 문자열을 의미합니다.
따라서 다음 구조면 충분합니다.
q0: 시작 상태 (비수용)
q1: ‘0’을 읽은 상태
q2: ‘1’을 읽은 뒤 수용 상태
q2 —ε→ q0 (반복 연결)
전이 관계:
q0 —0→ q1
q1 —1→ q2
q2 —ε→ q0
수용 상태: q2
시작 상태: q0
2. 검증 포인트
가. 입력이 “01” → q0→q1→q2 → 수용 (O)
나. 입력이 “0101” → q0→q1→q2→ε→q0→q1→q2 → 수용 (O)
다. 입력이 ε(빈 문자열) → q0 (비수용) → 거절 (O)
즉, (01)+ 형태에 완벽히 일치합니다.
3. 작성하신 NFA 피드백
가. (01)* 부분은 상태가 너무 많아요 (0~7까지 필요 없음).
나. (01)+ 그림은 거의 완벽합니다. 단, 시작 상태는 비수용으로 표시해야 정확합니다.
다. ε 전이는 q2→q0 한 번만 있으면 충분합니다.
정리하자면, 지금 구조 자체는 잘 이해하셨고, 불필요한 상태와 ε 이동만 줄이면 완전한 NFA 형태입니다.
즉, 3개 상태(q0, q1, q2) 로 간단히 표현하면 가장 깔끔한 정답이에요.