Computer Science Fundamentals Algorithms Subjective
Mar 05, 2013

How one can create RE of a particular language?

Detailed Explanation

First thing about RE and FA is that there is no hard and fast formula or method to generate these. One can generate them by its mental approach. And this mental approach can be acquired through only PRACTICE.
Here are some useful tips to write RE’s,
Let our language consist of the words of length three exactly over alphabet Σ= {a,b}
then it consists of the words L = {aaa, aab, aba,abb,baa,bab,bba,bbb}.
Its RE can be simply written as RE = aaa + aab + aba + abb + baa + bab + bba + bbb
which simply means that our language consists of only these words. So we can make RE for a finite language by writing its all words with + operator between them.

We should also keep the null string in our mind. If our language generates null string than our RE should also generate it)
For example language having all the words of even length has null string in it as well so we can write its RE as follows
                            RE = ((a+b)(a+b))*
This RE also generates null string.
If a language generates all strings starting with a. then strings will be of type a , aa, ab, aab, aaa, aba, abb,….
Here RE should start with ‘a’ and then all strings including null. So this will be (a + b)* and complete RE is a (a+ b)*.
Similarly languages of strings ending in b will have RE (a + b)*b.

Discussion (0)

No comments yet. Be the first to share your thoughts!

Share Your Thoughts
Feedback