컴파일러2장연습문제

소개글

컴파일러 2장 연습문제
홀수번호가 대부분입니다.
참고하세요

목차

없음

본문내용

2.1 다음 괄호에 알맞은 말을 쓰시오.
⑴ u와 v가 스트링일 때 |uv| = ( |u| + |v| )이다.
⑵ ωR은 스트링 ω의 ( 역순 )인 스트링을 나타낸다.
⑶ 알파벳 T에 대하여 언어 L은 ( T* )의 부분 집합이다.
⑷ 무한 언어를 유한 표현으로 나타내는 방법에는 세 가지가 있는데, ① 집합으로 조건 제시법, ② 언어 생성 시스템인 문법, ③ 언어의 ( 인식기 ) 등이다.
⑸ ( nonterminal 심벌 )은 문법에서 스트링을 생성하는데 사용되는 중간 과정의 심벌로 언어의 구조를 정의하는데 사용된다.
⑹ terminal 심벌과 nonterminal 심벌을 합해서 ( 문법심볼 )이라하며 보통 V(vocabulary)로 나타낸다.
⑺ 생성 규칙의 형태가 A → αAβ 와 같은 생성 규칙을 ( embedded )라 부른다.
⑻ 형식 언어 이론에서 주로 사용하는 증명 방법에는 ( 귀납 증명법 )과 모순 증명법이 있다.
⑼ 문법을 생성 규칙에 따라 4가지로 분류한 사람은 ( Noam Chomsky )이다.
⑽ ( 유한 ) 언어란 그 언어에 속하는 스트링을 일정한 순서로 열거할 수 있는 알고리즘을 갖는 언어를 말한다.
⑾ type 0 언어를 인식할 수 있는 인식기는 ( Turing Machine )이다.
⑿ 회문 언어(palindromic language)의 형태는 ( ωωR )이다.

2.3 다음 용어에 대한 정의를 쓰시오.
⑴ empty 스트링에 대한 정의
스트링의 길이가 0인 것을 empty 스트링이라 하며 ε으로 표기하고, 어떤 스트링 u, v에 대하여 다음과 같은 속성이 있다.
uε = u = εu
uεv = uv

⑵ 언어 L과 L`의 곱(production)에 대한 정의
두 언어 L과 L`에 속하는 스트링을 접속한 것으로 간단히 LL`으로 나타낸다.
LL` = {uv | u∈L 그리고 v∈L}

참고 자료

없음