Word problem(Decision Problem), Complexity and computing models
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) |
- 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.
- Complexity of type 1 word problem is very possibly harder than NP. Every known algorithm needs exponential time in worst case.
- 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|
[+] click to leave a comment [+]
the comment system on this blog works via email. The button below will generate a mailto: link based on this page's url and invoke your email client - please edit the comment there! [optional] even better, encrypt the email with my public key - don't modify the subject field - specify a nickname, otherwise your comment will be shown as anonymous - your email address will not be disclosed - you agree that the comment is to be made public. - to take down a comment, send the request via email.>> SEND COMMENT <<