## Special Cases: Examples

Please see Special Cases: Examples before following the answers to the given questions.

The same type of problem we already solved in several previous examples like

Example 1 and Example 1- it is NCFL but not DCFL.

–  Example 1it is NCFL but not DCFL.

– Example 1it is NCFL but not DCFL.

In some cases, there is another symbol that represents string same as

But x is not part of language so, we are not considering it.

This given language is similar to language

But it doesn’t affect the type or nature of language.

Initially, we try to write a regular expression for this given language.

and

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

To explain properly take an example

Let,

We can’t derive this string from the above RE,

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

Now, as per above example for all string is not accepted by the above-defined Regular Expression (RE).

So, we can’t write Regular expression for

Now,

This given language similar to language

The only difference that the range of x which doesn’t affect the type of the language.

So, the same way as the previous Example 2 we cannot write Regular Expression for this given language

So, same as Example 2,

This given language similar to language

The only difference that the range of x which doesn’t affect the type of the language.

Now, we can try to write a Regular Expression,

Here first and the last letter is same as either a or b because we know,

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

Example:

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

Take an example

Let,

So, we can visualize like that

We can expand x because

Take another example

Let,

Now,

Here we also can write the expression as

In the same way, we can expand x because

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