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 memory.
• This is a member of the Context Free Languages.
• You can fix up FSAs to become Push Down Automatas (PDAs) by adding a stack.
• 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.