컴파일러 연습문제 종합

목차

없음

본문내용

3.4 다음 정규 언어에 해당하는 정규 표현을 쓰시오.
(1)L1={anbm | n 0,m1}

a에 있는 n은 ε을 포함하기 때문에 a*로 표현할 수 있다.
b에 있는 m은 ε을 포함하지 않기 때문에 bb*로 표현된다. bb*=b+
답)a*b+

(2)L2={anbm | (n+m) is even}
n+m이 짝수가 되려면 n과 m이 모두 짝수이거나 홀수이어야 한다. 짝수는 2n으로 나타낼 수 있고, 홀수는 2n+1로 나타낼 수 있다.
(aa)*a·(bb)*b + (aa)*·(bb)*
위에서 앞의 부분은 홀수를 나타내는 부분으로 *가 되야 하나의 스트링도 표현할 수 있다.
뒤의 부분은 스트링이 아예 없을 경우도 있기 때문에 *되어야한다.

(3)L3={abnω | n 2,ω∈{a,b}*}
ω은 정규표현으로 (a+b)로 표현 될 수 있다.
bn 이n 2을 만족하기 위해서는 b+b가 되어야만 한다.

답)ab+b(a+b)*

3.5 다음 정규 문법이 생성하는 언어를 정규 표현으로 나타내시오.
1) S -> aA | bS
A -> aS | bB
B -> aB | bB | ε

위의 정규 문법을 정규 표현식으로 구성하면 다음과 같다.
S = aA + bS ‥‥‥‥‥‥‥‥(1)
A = aS + bB ‥‥‥‥‥‥‥‥(2)
B = aB + bB + ε ‥‥‥‥‥‥‥‥(3)

식(2)가 X=αX+β 같은 형태가 아니므로 넘어간다.

식(3)이 X=αX+β와 같은 형태이므로 을 풀면
B = (a+b)B + ε
= (a+b)*ε
= (a+b)* ‥‥‥‥‥‥‥‥(4)

식(4)를 식(2)에 대입하면
A = aS + bB
= aS + b(a+b)* ‥‥‥‥‥‥‥‥(5)

참고 자료

없음

압축파일 내 파일목록

7장연습문제풀이(컴파일러).hwp
compiler6장연습문제풀이.hwp
컴파일러3장.hwp
컴파일러3장연습문제.hwp
컴파일러_2장.hwp
컴파일러_2장_풀이.hwp
컴파일러_3장.hwp
컴파일러_3장[1]_풀이.hwp
컴파일러_4장_(2).hwp
컴파일러_4장_.hwp
컴파일러_5장_풀이(2).hwp
컴파일러_5장_풀이.hwp
컴파일러구조(Report-4).hwp