Context Free Languages
- There are languages you can't generate or recognise with an FSA.
- An example is a series of xs of length n followed by a y, then another
series of xs of the same length n.
- The problem here is that you need memory of n, and FSAs don't have
- This is a member of the Context Free Languages.
- You can fix up FSAs to become Push Down Automatas (PDAs) by adding a
- It is largely agreed that natural language is about this powerful.
- There are other languages that PDAs can't recognise.
- Context Sensitive Languages
- Continuing with these types of languages, you can replace the stack
with an infinite tape. This gives you a Turing machine.
- That's formally as powerful as any programming language (e.g.
Java, C, or Haskel).
- That is, any program that can be written in one language (e.g. C),
can be written in another (e.g. Java), or on a Turing machine.