[20하계] 모각코 4회차 결과

오늘은 계산이론 기말고사를 위해 공부를 하였다. 단원별로 어떤 내용을 배웠는지 정리하며, 문제를 풀어보았다. 기말 범위에 해당하는 내용들은 목차만을 정리해보았는데, 목차는 다음과 같았다.

 

> 정규 언어의 성질

문법간의 동치성, 피전홀 원리, 펌핑 보조 원리

> 문맥 자유 언어 (CFL)

파싱 (번역기, 컴파일러 등 다른 번역에 용이함), 유용한 많은 언어는 정규언어가 아니다. 

문맥 자유 문법은 오른쪽에 제한이 없으며 왼쪽에는 단일 변수만을 사용한다.

Context Free Language OR Grammar

좌측 우선 유도, 우측 우선 유도, 문장 형태와 유도 트리와의 관계, 파싱의 모호성과 소속성

문법과 언어의 모호성 (트리가 1개 이상 유도될 경우에)

> 문맥 자유 문법의 단순화와 정규형

유용한 치환 규칙, 쓸모없는 생성 규칙을 제거하고 람다 생성 규칙을 제거한다. 그 다음 단위 생성 규칙을 제거하여 문법을 단순화한다.

정규형: 촘스키 정규형과 그래비치 정규형

문맥 자유 문법에 대한: 소속성 알고리즘, CYK 알고리즘

PDA (푸쉬다운 오토마타) -> 문맥 자유 언어 CFL을 처리하기 위한 계산 모델

NPDA (비결정적 푸쉬다운 오토마타)

내부 상태/ 입력 기호/ 리스트 집합/ 초기/ 초기 기호/ 최종 상태

튜링 기계: 언어 승인 기술, 변환기로써의 동작에 대해

그 외 블록 도표의 사용 예, 매크로, 의사코드, 튜링 명제 등을 배웠으며, 

동등성 스테이 옵션, 일반 무한 기계, 다차원 튜링 기계, 비결정적 튜링 기계, 범용, 선형 한정 튜링 기계