오토마타와 형식언어 정리

created : 2021-10-19T12:46:37+00:00
modified : 2021-12-26T08:51:01+00:00

Chapter 1. Introduction

1.2 Three basic concepts Languages

String Operations

Grammars

Automata

Chatper 2. Finite Automata

2.1 Deterministic Finite Automata (DFA)

Determistic Finite Automata (DFA)

Extended Transition Function $\sigma^*$

Languages Accepted by DFAs

Regular Languages

Non-determistic automata(NFA)

$\lambda$ - transition

Formal Definition of NFAs

Extened Transition Function $\sigma^*$

Why Nondeterminism?

\[\begin{aligned} S \rightarrow ab \vert aaA \\ A \rightarrow aaA \\ A \rightarrow abbc \vert abaAc \end{aligned}\]

Parsing

1) Removing $\lambda$ - productions

9.2 Combining Turing machines for complicated tasks

Combining TMs

9.3 Turing’s Thesis, 튜링 명제(가설))

Turing’s Thesis 뒷받침 하는 것들

Definition of Algorithm

Chapter 10 Other Models of Turing Machine

The Standard model

10.1, 10.2: Variations of the Standard Model

10.3 Nondeterministic Turing Machines

Theorem 10.2

10.4 A Universal Turing Machine

Universal Turing Machine

Set Theory(집합론), (Un)countable Sets, Enumeration Procedure

Theorem 10.3:

Enumeration Proceduer


Chap 11 A Hierarchy of Formal Languages and Automata

Recursively Enumerable(r.e.) Languages

Recursive Languages

Languages that are Not Recursively Enumerable

Theorem 11.1

-Theorem 11.5

11.2, 11.3 Unrestricted Grammars & Context-sensitive grammars

Unrestricted Grammar

Context-sensitive Grammar

Context-sensitive language

11.4 The Chomsky Hierarchy

Chap 12 Limits of Algorithmic Computation

12.1 Problems that cannot be solved by TMs

The Halting Problem(HP)

### Undecidable problems for CFL

  1. Is a cfg unambiguous?
  2. Are two cfg’s equivalent?
  3. Do two cfg’s generate any common string?