Automata theory: understanding different automata

[Avichal]

Move this thread to appropriate sub-forum if not here.

I'm studying automata theory and I'm having trouble understanding different machines or automata.
First one is regular language. This is the simplest machine with different states and we can switch depending on what our input is. Very well till here.

Then comes context-free languages. Now I fail to understand the need to study this machine. Along with different states it has a stack to. So in someway it can count also.
I get a little bit of intuition but not completely.

I don't understand need to study context-free language and turing-complete language? I need the intuition

 

[Greg Bernhardt]

I'm sorry you are not finding help at the moment. Is there any additional information you can share with us?

 

[FactChecker]

My two cents: A stack can provide order of events / operations that is far easier than defining states for every possible sequence. Ten items can be put into 3.6 million different orders (permutations) in a stack. Imagine trying to define a state for each possible order.

 

[AlephZero]

Regular languages are easy to implement but they are too restrictive for many applications.

You can't describe many "simple" features of the a language using only a regular grammar. For example you can't write a regular grammar that will recognize the (infinite number of) strings

ab, aabb, aaabbb, aaaabbbb ... etc, where the string contains an arbitrary number of a's followed by the same number of b's.

That isn't just a "made up" example. It is the first step towards recognizing if pairs of characters like { } [ ] ( ) are correctly nested (to any depth) in the syntax of a programming language like C, Java, etc.

You could easily write a computer program to recognize strings like the above example, by using a variable to count the number of a's, and then count the same number of b's. In a context-free language, a stack can do that sort of counting operation, by push things onto the stack and popping the same number of things off it.

Context-free languages and Turing complete languages are needed to deal with "real world" situations that are too complex for regular expressions.