61 views

+1 vote

language $L1$ : $L1$ is not Regular, Not even DCFL.. Why?

In $L1$, All strings are of even length And We are required to find the Middle of the String..because In the First half part we can't have $c$ and in the next half part we can't have $a$. But Finite automaton do not have the power to find the Middle.

language $L2$ : $L2$ is regular.

language $L3$ :  $L3$ is CSL.

language $L4$ : $L4$ is Non-regular because there could come(occur) any number of $ac$ without any $abc$ occurrence. And So, After that we would need to remember how many $ac$ have occurred etc. Such things are not possible for $FA$ So, Non-regular.

• ## L1 is regular .

Regular exp= (aa+bb+ab+ba)*.(bb+cc+bc+ca)*

• ## In L4 also there is comparison .so it is also non regular.

edited
+1
sir, i am not getting how the L1 is regular?  and moreover there are three symbols but you used only 2 can you briefly explain please.
0
I think now it is right. i am not sure about regular expression. But it is look like regular.
0
The regular expression for $L1$ is not correct. $L1$ is not even Regular because we need to find the middle of the string for string to accept.
0
L1 is not regular and not dcfl it is CFL only

But I didn't understand tht why 2 is regular

PlZ explain it
0

consider this DFA for L2