Grammas describe languages as a set of words that the gramma could generate. The word problem is to determine, whether a given word belongs to the language.

German version of this post
NOTE: MOST CONTENT OF THIS POST ARE TAKEN FROM:

Lecture scripts by Prof. Dr. Markus Krötzsch, TU Dresden

---

§ The Word problem

The Word Problem: to determine whether a word is in a language.

• INPUT: a word $w \in \Sigma^\star$
• OUTPUT: true when $w \in L$ , false when $w \notin L$

It is also referred to as the Decision Problem.

§ Decidability

A language $L \in \Sigma^\star$ is decidable if its characteristic function $\chi_L: \Sigma^\star \to \{0,1\}$ is computable: for every given word, it can be determined whether it IS or IS NOT in L.

$$\chi_L(w) = \begin{cases}1 , &w \in L \\\\ 0 , &w \notin L \end{cases}$$

A language $L \in \Sigma^\star$ is semi-decidable: a given word can be justified that it IS in L, but it can’t be decided whether it is NOT in L.

$$\chi_L(w) = \begin{cases} 1 , &w \in L \\\\ \text{undefined}, &w \notin \end{cases}$$

Or vice versa:

$$\chi_L(w) = \begin{cases} \text{undefined}, &w \in L\\\\ 0 , &w \notin L \end{cases}$$

§ Complexity and Computing Models

For some languages the word problem is easy. for example: $L: \{a\}\circ\{b\}^\star$

The word problem of L can be solved in linear time: first exam whether the first letter is a, then determine whether all following letters are b

However the word problem can be super hard.

Overview

Language Class	Computing Model	Complexity of Word Problem
Type 0	Turing machine (TM)	semi(or non-)decidable(1)
Type 1, Context sensitive	Nondeterministic TM with linear space	PSpace-Complete(2)
Type 2, Context free	Nondeterministic Pushdown Automaton	Polynomial
Type 3, Regular	Finite State Machine	Polynomial(3)

1. for type 0, acceptance of a word can be arbitrary long process, we don’t know if the process still goes on when there isn’t a match yet.
2. Complexity of type 1 word problem is very possibly harder than NP. Every known algorithm needs exponential time in worst case.
3. Word problem of Type 3 is actually much easier than Type 2.

§ further Problems to be discussed:

Description(or representation) of Languages

• what different descriptions of languages are there (Grammas, Automaton etc.)?
• how to translate among different descriptions of languages?
• Do 2 descriptions of languages actually describe the same language?
• Does a description describe a empty language?
• how to simplify a Description of language?

Characteristics of languages

• What will happen if we perform operations upon languages? For example: L1 and L2 are both regular, is $L1 \bigcap L2$ regular?
• Closure

|end|

---