컴파일러 제 3장 연습문제

소개글

컴파일러 입문 (정익사) 3장 전체 연습 문제 입니다.

목차

3.1 다음 괄호에 알맞은 말을 쓰시오.
3.2 다음 질문에 대한 답을 하시오.
3.3 α, β, γ가 정규 표현일 때 다음을 증명하시오.
3.4 다음 정규 언어에 해당하는 정규 표현을 쓰시오.
3.5 다음 정규 문법이 생성하는 언어를 정규 표현으로 나타내시오.
3.6 다음과 같은 DFA가 주어졌을 때 물음에 답하시오.
3.7 다음과 같은 NFA가 주어졌을 때 물음에 답하시오.
3.8 다음 NFA를 DFA로 바꾸시오.
3.9 다음 FA를 보고 물음에 답하시오.
3.10 다음 FA가 인식하는 언어 L(M)을 정규 표현으로 나타내시오.
3.11 다음 DFA를 도달 불가능 상태를 갖지 않고 모든 상태가 구별 가능한 축약된 FA(reduced FA)로 바꾸시오.
3.12 다음과 같은 2개의 유한 오토마타가 주어졌을 때 물음에 답하시오.
3.13 정규표현 r = ab*a* 가 주어졌을 때, 물음에 답하시오.
3.14 다음과 같은 정규 표현을 인식하는 DFA를 구성하시오.
3.15 다음 정규 표현을 생성하는 정규 문법을 고안하시오.
등..

본문내용

3.1 다음 괄호에 알맞은 말을 쓰시오.
① 정규 언어를 표현하는 방법에는 정규 문법, 정규 표현, ( 유한 오토마타 ) 등 3가지가 있다.
② 정규 표현의 기본 소자는 ϕ ,ε, 그리고 ( terminal 심벌 )이다.
③ 일반적인 명칭의 형태를 정규 표현으로 나타내면 ( letter(digit+letter)* )가 된다.
④ α가 정규 표현일 때 α* + α+ = ( α* )이다.
⑤ α, β가 정규 표현이고 ε ∉ L(α)이면, X = αX+β의 유일 해는 X = ( α*β )이다.
⑥ 일반적으로 언어에 대한 ( 인식기 )는 입력으로 스트링을 받아 스트링이 그 언어의 문장이면 “yes"를 답하고 그렇지 않으면 ”no"를 답하는 기능을 행한다.
⑦ δ(q, a) = {p1, p2, … , pn}의 의미는 q 상태에서 입력 a를 본 ( 다음 상태 )는 p1부터 pn 중에 하나를 선택할 수 있다는 것이다.
⑧ NFA를 DFA로 변환하면, DFA의 상태 수는 이론적으로 ( 2Q -1 )개가 된다.
⑨ δ 함수의 정의가 δ: Q×(∑∪{ε}) → 2Q인 유한 오토마타를 ( ε-NFA )라 부른다.
⑩ 상태 수를 최소화하는 방법은 ( 동치관계 )를 이용하여 상태들을 합침으로써 상태 수를 최소화하는 것이다.
⑪ 들어오는 지시선이 없이 나가는 지시선만 갖는 상태를 ( 도달 불가능 상태 )라 부르며 모두 제거할 수 있다.
⑫ 유한 오토마타를 정규 표현으로 직접 바꿀 수는 없고 반드시 ( 정규 문법 )으로 바꾼 후 정규 표현을 얻게 된다.
⑬ 유한 오토마타를 정규 문법으로 바꾸었을 때, 생성 규칙의 개수 |P| = ( |δ| + |F| )이다.
⑭ 정규 언어는 합집합, 접속, 그리고 ( 클로저 )에 대하여 닫혀 있다.
⑮ 어떤 언어가 정규 언어가 아님을 증명하는데 유용한 보조 정리를 ( 펌핑 렘마 )라 부른다.

3.2 다음 질문에 대한 답을 하시오.
① 우선형 문법 S → 00S | 1S | 0을 동등한 좌선형 문법으로 바꾸시오. S = (00 + 1)*0

S → A | 0
A → S00 | S1

참고 자료

컴파일러 입문