소개글
대학교때 연습문제 풀이 해놓은 겁니다.
목차
3장
3.1
3.2
3.4
3.5
3.6
3.7
3.8
3.9
3.10
3.11
본문내용
3.1 다음 괄호에 알맞은 말을 쓰시오.
(1) 정규 언어를 표현하는 방법에는 정규문법, 정규표현,(유한 오토마타)등 3가지가 있
다.
(2) 정규 표현의 기본 소자는 ø, ε, 그리고 (terminal 심벌)이다.
(9) δ 함수의 정의가 δ : QX(∑∪{ε})->2Q인 유한 오토마타를 (ε-NFA)라 부른다.
(10) 상태수를 최소화하는 방법은 (동치관계)를 이용하여 상태들을 합침으로써 상태수
를 최소화하는 것이다.
3.5 다음 정규 문법이 생성하는 언어를 정규 표현으로 나타내시오.
1) S -> aA | bS
A -> aS | bB
B -> aB | bB | ε
답 :
정규 표현식
S = aA + bS ‥‥(1)
A = aS + bB ‥‥(2)
B = aB + bB + ε ‥‥(3)
(3)을 풀면
B = (a+b)B + ε
= (a+b)*ε
= (a+b)* ‥‥(4)
그러므로,
L(G) = (aa+b)*ab(a+b)*
참고 자료
없음