정규식과 정규 문법
정규식 (Regular Expressions) 언어는 집합으로 표현되고, 집합 연산자를 통해 새로운 언어를 표현합니다. 이때, 집합 대신 간결한 정규식으로 대신하여 사용합니다. 집합 연산자 ∪, *, ·, 는 각각 정규식 연산자인 +, *, ·(생략 가능) 으로 치환됩니다. 정규식은 정규 언어의 표현을 단순화 한것이므로, 실제로는 정규 언어를 의미합니다. ex) {a} = a, {a} ∪ {b} ∪ {c} = a+b+c ... etc 기호 ∑에 대해서, 1. Ø, λ, a ∈ ∑ 는 정규 표현입니다. 2. 두 정규 표현 r1, r2가 주어졌을 때, r1+r2, r1r2, r1*는 정규 표현입니다. 3. 1, 2로 얻어지는 식은 정규 표현입니다. 4. 1, 2, 3에 의해 유도되지 않는 표현은 정규 표현이..
2023. 12. 26.
유한 오토마타 (Finite Automata)
결정적 유한 오토마타 (Deterministic Finite Automata) 결정적 유한 오토마타는 저장 기능이 없는 오토마타입니다. DFA의 정의는 다음과 같습니다. M = (Q, ∑, δ, q0, F) 여기서 Q는 유한개의 상태의 집합입니다. ∑는 유한개의 입력 기호의 집합이고, δ는 Q X ∑ → Q 의 전이 함수입니다. q0의 위치에 시작 상태가 들어가고, F에 최종 상태가 들어갑니다. 이때, F는 여러 개일 수 있습니다. DFA는 위 정의에 의해 초기상태인 Q0에서 시작하여, 입력 스트링의 가장 왼쪽에 위치한 입력 포인터가 오토마타의 전이에 의해 하나 왼쪽으로 전진하며 소비합니다. 입력 스트링이 모두 소비되고, 오토마타가 F에 있을 경우, 해당 스트링은 오토마타에 의해 승인된 스트링이고, 아닐..
2023. 12. 25.