The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

asked in Theory of Computation by Junior (779 points) | 129 views

2 Answers

+2 votes

Answer : Option A

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.

answered by Boss (24.1k points)
+1 vote

Option b

  • L1 is regular .

Regular exp= (aa+bb+ab+ba)*.(bb+cc+bc+ca)*
  • L2 is also regular.

  • In L3  comparison between a ,b and c .so it is non regular

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

answered by Boss (33.6k points)
edited by
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.
I think now it is right. i am not sure about regular expression. But it is look like regular.
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.
L1 is not regular and not dcfl it is CFL only

But I didn't understand tht why 2 is regular

PlZ explain it

consider this DFA for L2

Related questions

0 votes
1 answer
asked Jun 6, 2018 in Theory of Computation by Shivani gaikawad Junior (779 points) | 40 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,408 questions
53,589 answers
70,871 users