A very, very high-level approach to computing theory — EP2
Hello, one more time reader, I'm once again with a new chapter in this series of a high-level introduction to computing theory and if you are new to this series ill put the link to the first part where we talked a little about alphabets, languages, and DFAs in the geek culture blog right here.
So first of all in the last article, we discussed that DFAs are deterministic language recognizers and that I always know which state the machine is going to move to, but for very complex regular languages it turns the automata very hard to understand and to link all the transitions between states, that's where our friend NFA comes to the party:
— NFAs
In order to minimize the complexity of many transitions and many states we count with the guessing power of an NFA that basically creates multi copies of the machine to guess which state it should be and if the whole sequence is read and an instance of the machine is in a final state the automata recognize the language, and the opposed if the copy of automata cant continue it just gets deleted
And we can see by the automata that the example on the left recognizes the binary language that contains {0,1} where the last character of the sequence is 1, but we can also notice that there are two transitions when I read the symbol 1 at the same moment that's where the NFA tries to guess if the one we are reading is the last one or is in the middle of the sequence.
If we are reading sequence 011 the automata will read the zero and will stay in the p state, but when we read 1 the NFA will create one more copy of the machine(similar to a second process in the operating system) one of the copies will stay in the p state and the other one will go to q and after that, the NFA will read the last 1 and the instance of the machine that was in p will get deleted because I'm reading symbols in a state that there are no transitions and the machine that was in p state will create another copy in the q state the machine that read the last one in p state will not have any symbols to read and will not be accepted by the machine, but the copy with the q state active will not have any more symbols to read and as soon as q is a final state the sequence 011 will be accepted.
And now that we go through the basic workflow of an NFA if you are asking yourself: “Are NFAs better than DFAs?”. The answer is no, both DFAs and NFAs are mathematically equivalent and both of the machines can recognize regular languages, the main difference is that with NFAs I don't know exactly where the machine is because I can have many states in many copies of the machine, but I gain a guessing power using NFA not needing to specify every transaction, and at the end, if you have a language and need to prove that this language is a regular language you can create an NFA, DFA or a Regular Expression they are all equivalent and if successful your language is certainly a regular language
— Regular Expressions
You probably heard about regular expressions before and probably also have copied a regex from stack overflow that you wasn't very sure how it worked, well now you know that regular expressions are part of the computing theory field, but on the contrary of NFAs and DFAs a regular expression generate a regular language sequence instead of recognizing.
The properties of regular expressions:
— Union
Similar to an or statement, I can generate sequences containing one or the other symbol like in a language that I have the symbols [A, B] I can represent that with A U B (A or B).
— Concatenation
It's like a glue between the elements, I can generate sequences containing both of the symbols like in a language that I have the symbols [A, B] I can represent that with A . B (AB).
— Star operator
Its exponential repetition of a symbol randomly going from 0 to infinity like in a language that I have the symbol [A] I can represent that with A* ({}, A, AA, AAA, A…n).
Let's generate the sequence in the first NFA for the language: “{0,1} where the last character of the sequence is 1”. our regular expression would be 0*.1*.1
And the above regular expressions can generate all the possible inputs for the language described, and I just needed to generate the star for the 0 and 1 symbols that can generate symbols of *n(star of integer number n), and then concatenate the 0* and 1* symbols and by last, I just added a last .1 to the expression that is useful for example if my n is zero my sequence will be empty “ ”(no 0 and no 1 symbols) and the sequence would be rejected by the NFA, but if I append a last 1 symbol the NFA will go directly to the final state and will accept the sequence
Todays article is a bit shorter than the last one but now that I covered NFAs and Regular expressions i still keep recommending you to go deeper into computing theory,it is a very mature topic in computer science and also very fascinating with many applications in the real world.
I also want to thank you all for reading my last article, it was amazing we got featured in the dev URLs and the article was invited to be published in the geek culture blog. So grateful for all of you guys.
Now we covered the DFAs, NFAs, and regular expressions in topics in computing theory still, there's a lot to dig into like free context grammars, pushdown automaton, Turing machines, Grammatics, and more so stay tuned. See ya :)