봄수의 연구실

유한 오토마타 어떤 알파벳 Σ로부터 만들어지는 문자열의 특별한 것들을 받아들이는 시스템의 수학적 모델로서, 그 시스템에서 변화할 수 있는 상태가 유한개이다. 컴퓨터의 여러 분야에서 널리 사용되고 있다. 특히 플립플롭(flip-flop)을 비롯한 여러 컴퓨터 관련 고안물들, 형식언어의 연구, 그리고 컴파일러 등에 유용하게 쓰인다 또, 컴파일러의 어휘 분석(lexical analysis) 또한 유한 오토마타의 대표적인 것이다. 상태 전이 함수의 형태에 따라 결정적 유한 오토마타 (Deterministic Finite Automata; DFA)와 비결정적 유한 오토마타(Nondeterministic Finite Automata; NFA)를 구분한다. 오토마타의 전이 함수는 유한 오토마타의 상태 전이를 행렬(m..

BNF 표현 방법 BNF (Backus-Naur Form)는 프로그래밍 언어의 형식적 정의(formal definition)을 위해 가장 널리 사용되는 방법입니다 이 표기법은 메타 기호(meta-symbol; 메타기호는 표현하려는 언어의 일부분이 아니라, 그 언어를 표현하려고 사용된 특수기호)로서 세 가지 기호를 사용합니다 논터미널기호는 로 묶어 표현 대체(replacement)는 ::= 사용 양자택일은 | 를 사용 예제 3.24 BNF로 표현하기 1 논 터미널 기호인 E,T,F는 각각 , , 로 나타난다. → 는 ::= 로 표시한다 P: ::= + | - | ::= * | / | ::= () | id 예제 3.25 BNF로 표현하기 2 첫 번째 기호가 영문 소문자로 시작하고, 두 번째 기호부터는 영문 ..

정규 문법 표현하는 방법 해당 글은 정규 문법의 연산 순서의 양줄이기 버전입니다 정규 문법을 가장 잘 표현 할 수 있는 방법에 대해 알아보자! 위의 정의에서 연산자의 우선 순위는 *(클리니 클로저) > •(접속) > +(합집합)이다. 사칙 연산과 동일하게 왼쪽 결합 법칙 이 적용 된다 예제. 다음 정규 표현의 연산 순서는? 앞서 말한, 연산자 우선 순위와 왼쪽 결합 법칙을 이용하면 위와 같은 연산 순서를 가지게 된다. 이렇게 보니, 사칙 연산과 동일하다 생각해도 될 듯하다 예제 3.20 정규표현에 의해 생성 되는 언어 0 + 1은 언어 {0 , 1 }을 나타낸다 (0 + 1) 0은 {00, 10}을 나타낸다 0*는 언어 { ε, 0, 00, 000, ⋯}를 나타낸다 (0 + 1)*는 언어 {ε, 0, 1..

정규 문법(regular grammar) 모든 규칙이 다음과 같은 형태를 가지는 문법을 말합니다. A -> aB A -> a A -> ε A와 B는 비터미널 심볼(nonterminal symbol) a는 터미널 심볼(terminal symbol) ε는 빈 문자열(empty string)을 나타냅니다. 정규 문법은 주로 언어의 구문 분석에 사용되며, 정규 표현식(regular expression)과 같은 형식 언어(formal language)의 기본적인 표현 방법 중 하나입니다. 비터미널 심볼(nonterminal symbol) 다른 비터미널 심볼 또는 터미널 심볼로 대체될 수 있습니다. 예를 들어 위의 정규 문법에서 A가 다른 비터미널 심볼이나 터미널 심볼로 대체될 수 있다는 의미입니다. Right-l..