컴파일러 형식언어 연습문제 2장 괄호 풀이
본 자료는 3페이지 의 미리보기를 제공합니다. 이미지를 클릭하여 주세요.
닫기
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
해당 자료는 3페이지 까지만 미리보기를 제공합니다.
3페이지 이후부터 다운로드 후 확인할 수 있습니다.

소개글

컴파일러 형식언어 연습문제 2장 괄호 풀이에 대한 보고서 자료입니다.

본문내용

지나, 레온하르트 오일러는 모든 짝수 완전수는 2n-1(2n 1)의 형태라는 것을 증명했다. 즉 짝수 완전수와 메르센 소수 사이에는 일대일 대응이 있다는 것이 밝혀졌다. 메르센 소수의 수가 유한한지 무한한지는 알려져 있지 않다. 그러므로 완전수의 수가 무한한지도 알려져 있지 않다.
홀수 완전수
홀수 완전수가 존재하는 지는 아직 알려져 있지 않다. 적어도 10300 까지의 정수 중에는 없다는 것이 확인된 바 있다.
완전수와 더불어, 진약수를 더해서 자기 자신보다 적은 수를 부족수, 많은 수를 과잉수라 부른다. 서로의 진약수를 더하면 상대편이 되는 두 수는 친화수라 부른다.
정의 3.1
문법을 구성하고 있는 각 생성 규칙의 형태가 다음과 같을 때 정규 문법이라 한다.
⑴ A → aB, A → a, 여기서 a∈VT 이고 A, B ∈VN 이다.
⑵ 만약 S → 이면, S가 다른 생성 규칙의 오른쪽에 나타나지 않아야 한다.
3.2
정규 표현은 다음과 같이 정의된다.
1. 정규 표현의 기본 소자는 , , 그리고 terminal 심벌이다.
⑴ 는 공집합을 나타내는 정규 표현이다.
⑵ 은 집합 {}을 나타내는 정규 표현이다.
⑶ a∈VT 는 집합 {a}를 나타내는 정규 표현이다.
2. 만일 e1 e2가 정규 언어 L1 L2를 나타내는 정규 표현이라면
⑴ (e1)+(e2)는 L1∪L2를 나타내는 정규 표현이다.(union)
⑵ (e1) (e2)는 L1 L2를 나타내는 정규 표현이다.(concatenation)
⑶ (e1)*은 {} ∪ L11 ∪ L12 ∪ L13 … ∪ L1n ∪ … 을 나타내는 정규 표현이다.(closure)
3.위의 정의된 것 이외에 어떠한 것도 정규 표현이 될 수 없다. 단, (e1) (e2) 정규 표현은 편의상 (e1)(e2)로 나타내는 것이 일반적이며, e1+는 e1 e1*의 단축 표현(shorthand notation)이다. 또한 (e1)+(e2)는 (e1)|(e2)로도 표기한다.
3.3
α가 정규 표현일 때, L(α)는 α가 나타내는 언어를 의미한다. 이런 의미에서 α와 β가 정규 표현일 때, 정규 표현 정의에 따라 다음을 만족한다.
1. L(α+β) = L(α) ∪ L(β)
2. L(αβ) = L(α)L(β)
3. L(α*) = L(α)*
3.4
en 개의 정규 표현이 같은 언어를 표현할 때 그 정규 표현은 같다고 말한다. 다시 말해서, L(α) = L(β) 이면 α = β 이다.
3.5
계수(coefficient)가 정규 표현인 식을 정규 표현식(regular expression equation)이라 부른다.
3.6
FA M = (Q, Σ, δ, q0, F)
Q: 상태(state)들의 유한 집합
Σ: 입력 심벌(input symbol)의 유한 집합
δ: 사상 함수(mapping function)
q0: 시작 상태(start 또는 initial state) (q0∈Q)
F: 종결 상태(final state)의 집합을 의미한다.(F⊆Q)
3.7
DFA M = (Q, Σ, δ, q0, F)
Q: 상태(state)들의 유한 집합
Σ: 입력 심벌(input symbol)의 유한 집합
δ: 전이 함수로 QxΣ→Q, 즉 δ(q,a) = p 이다.
q0: 시작 상태(start 또는 initial state) (q0∈Q)
F: 종결 상태(final state)의 집합을 의미한다.(F⊆Q)
3.8
유한 오토마타(DFA) M에 의해 인식되는 스트링 전체를 모아 놓은 집합을 M에 의해서 인식되는 언어라고 말하며, L(M)으로 표기한다. L(M)의 정의는 다음과 같다.
L(M) = {x | δ(q0, x) ∈ F}
3.9
상태 전이도(state transition diagram) : 상태 전이도는 유한 오토마타의 각 상태를 노드(node)로 나타내고, 전이 함수 δ(q, a) = p 에 대해서 상태 p에서 q로 가는 리이블(label)이 a인 지시선(directed arc)로 나타낸다. 또한 종결 상태들은 이중 원(double circle)으로 표시하고 시작 상태는 start 지시선으로 표시한다.
3.10
유한 오토마타 M = (Q, Σ, δ, q0, F) 이 주어졌을 때, 모든 q∈Q와 a∈Σ에 대하여, δ(q, a)가 오직 한 개의 다음 상태를 가질 때, M은 완전히 명시되었다(completely specified)고 말한다.
3.11
NFA M = (Q, Σ, δ, q0, F)
Q: 상태(state)들의 유한 집합
Σ: 입력 심벌(input symbol)의 유한 집합
δ: 전이 함수로 QxΣ→2Q, 즉 δ(q,a) = {p1, p2, … , pn}이다.
q0: 시작 상태(start 또는 initial state) (q0∈Q)
F: 종결 상태(final state)의 집합을 의미한다.(F⊆Q)
3.12
유한 오토마타(NFA) M에 의해 인식되는 스트링 전체를 모아 놓은 집합을 M에 의해서 인식되는 언어라 하고 L(M)으로 표기하며 그 정의는 다음과 같다.
L(M) = {x | δ(q0,x) ∩ F ≠ }
3.13
-NFA에서 -CLOSURE의 정의는 다음과 같다.
1. s가 한 개의 상태인 경우, -CLOSURE(s)는 s와 s로부터 레이블이 인 지시선으로 도달항 수 있는 모든 상태들을 포함한다.
-CLOSURE(s) = {s} ∪ {p | δ(q, = p, q∈-CLOSURE(s) )
2. T가 하나 이상의 상태 집합으로 된 경우, -CLOSURE(T)는 T 속의 각 상태에 대해 과정 1과 같은 방법으로 상태들을 구하여 합 집합한 것이다.
-CLOSURE(T) = -CLOSURE(q)
3.14
ω∈Σ* 에 대해 만약 q1에서 ω를 다 본 상태가 q3이고 q2에서 ω를 다 본 상태가 q4일 때, q3, q4 중 하나만 종결 상태에 속하면 q1은 q2로부터 구별된다(distinguish)고 말한다.
3.15
다음 조건을 만족하는 유한 오토마타를 축약된 유한 오토마타(reduced finite automata)라 부른다.
⑴ 모든 상태가 시작 상태로부터 도달 가능하다.(accessible)
⑵ 모든 상태가 서로 구별 가능하다.(distinguishable)
  • 가격1,900
  • 페이지수11페이지
  • 등록일2020.12.09
  • 저작시기2007.8
  • 파일형식한글(hwp)
  • 자료번호#1141797
본 자료는 최근 2주간 다운받은 회원이 없습니다.
다운로드 장바구니