This post discusses membership problem of a language.

** what is membership problem of a language**

- Input: A string and a language
- Output: True if the string belongs to the language. False if the string doesn’t belong to the language.

** membership of recursively enumerable language **

- The problem is semi-decidable. It is only decidable when the answer is true.
- Let a program enumerate all strings in the language one by one. If the enumerated string so far matches the input string, then return true. This program will run forever and not return if the input string is not in the language.

** membership of recursive language **

- The problem is decidable.

** membership of context-sensitive language **

- A language is context-sensitive if the left hand side of production rules could have terminal or non-terminal symbols.
- The problem is decidable.
- The problem is in pspace-complete. There exists no polynomial time algorithm for this problem.

** membership of context-free language **

- A language is context-free if the left hand of production rules could only be non-terminal symbols. It implies that all production rules are context-free since it is deterministic for a non-terminal symbols no mater what is preceding or succeeding of it.
- The problem is decidable.
- There exist polynomial time algorithms to solve this problem. The time complexity is O(n^3).
- Reference: CYK algorithm and Earley parser

** membership of regular language **

- A language is regular if the all its production rules is left-linear or right linear.
- The problem is decidable.
- There exist polynomial time algorithms to solve this problem. The time complexity is O(n).
- Reference: Thompson’s construction

** conclusion **

This post discusses membership problem of a language, in terms of decidable and time complexity.

### Like this:

Like Loading...