A very, very high-level approach to computing theory — EP3
Hello again reader for our third episode in this series of computing theory, and wow it’s been a long, but pleasant(I mean I think you liked it, right?) journey, and again thank you all a lot for the feedback and for reserving your time to read, comment and give your feedback about this series, it made me super glad and makes me want to bring more and more good quality content here, by the way, if you still don’t read the previous chapter click here, and straight to the point, today is the day to talk about the free-context languages, differently from the regular languages the free-context languages are in another category of the Noam Chomsky’s order of languages.
An example of a non-regular language is a**n.b**n where n ≥ 1 using automata or regular expressions I can't figure out how many a’s I read to compare with how many b’s I read and see if they are the same amount, because both in NFA’s and DFA’s I have a finite number of states and with the Regular expressions I can't guarantee that my expressions elevated to the star operator will generate the same number of b’s and a’s.
So in order to solve this problem, new types of solutions are required, and they are:
— Pushdown Automaton
The name sounds like something very fancy and complicated, but if you know the stack data structure, you are almost there into understanding the pushdown automaton.
Similar to a DFA or an NFA we have our states and the addition of a stack structure, in the initial state we add an ending symbol like “$”, and when we read an “a” symbol we add the “a” symbol to the top of the stack(push), and after all the “a’s” read we start reading “b’s” and after reading a b symbol we remove the head of the stack(pop) if all the b’s were read and the head of the stack is the $ symbol the language a**n.b**n where n ≥ 1 was successfully recognized
— Free Context Grammars
Similar to a recursive function call, free context grammars generate free context languages and their operations are fairly simple.
To generate this language a**n.b**n where n ≥ 1 we’ll only need our variables and terminal symbols
-Variables
Call using recursion that ends up generating one terminal
-Terminals
Symbols that cannot generate other symbols
S -> AB
A -> aA | a&
B -> bB | b&
Here is the free context grammar that generates the language a**n.b**n where n ≥ 1, and as we can notice {S, A, B} are our variables because they are generating terminals {a, b and the &(symbol for epsilon or empty string)}
S produces (->) A(calls A)B(calls B)
A produces(->) either a(terminal)A(calls A) or a(terminal)&(“” terminal)
B produces (->) either b(terminal)B(calls B) or b(terminal)&(“” terminal)
And all the sequences generated are one hundred percent sure to generate sequences that contain the same number of a’s and b’s fitting in the definition of the language a**n.b**n where n ≥ 1 using the recursive calls to generator variables.
And here we are at the end of the third episode of this high-level approach to computing theory, it's been really fun to write about this amazing topic in computer science that has a huge importance on how we developed computation and modern software, and modern technologies.
Once again, thank you so much for reading till here and there are still many things to write about computing theory like churches lambda calculus, turning recognizable and decidable languages, context-dependent languages, ambiguous grammars, turning machines and many more, so I highly encourage you to dive more deeply into computing theory and see ya :)