Special Cases: Examples


Please see Special Cases: Examples  and Special Cases: Examples before start this section.




This given language is the same as 

because x is not present in that case.


So, this same problem already discussed in Example 2 please see for details.

And because there is no special character so, it needs multiple copies of the stack. 

For details see Example 2.




Like previous question Example 1


Now, we can try to write regular expression initially


But we can’t derive all the strings from the above RE.




We can’t derive this string from above, 

because it is always ending with either aa or bb, it never ends with ba or ab

So, as per above example for all string is not accepted in this,




This language same as above 

The only position of x is different but the logic is the same.

So, the same way as above us cannot write Regular Expression for this given language 

So, same as Example 2,


Now we first see that we can write a regular expression for it or not.

Here first and the last letter is the same as either a or b.  

In this expression, every string has the same starting and ending symbol, and a minimum three-length string.




Now we have to check this Regular Expression (RE) can cover all the strings of the given language.


Take an example 


So, we can visualize like that

and starting and ending symbol is the same.


Take another example 




Here we also can write the expression as 


and starting and ending symbol is the same.

Now, we can cover all string where ending and starting string is same.

So, we can form a regular expression for this language.