CREATE OWN LIBRARY

Special Cases: Examples

 

 

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

 

Answer:

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.

 

 

Answer: 

This given language is similar to language 

(Special Case Examples Example 2) 

 

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, 

 

Answer:

This given language similar to language 

(Special Case Examples Example 2) 

 

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,

 

Answer:

This given language similar to language 

(Special Case Examples Example 2)  

 

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.