The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
69 views
L1= Set of all strings having equal number of 00 and 11.
L2= Set of all strings having equal number of 01 and 10.
Which of the following is true?
(a) Both are Regular (b) Both are Context-Free
(c) L1 is regular, L2 is Context Free (d) L1 is CF, L2 is Regular
asked in Theory of Computation by Active (1.4k points) | 69 views
0
D will be answer
0

Visit this link..you will know why L2 is regular :)

https://gateoverflow.in/47443/isi2014-cs-4a

 

2 Answers

0 votes

L1 is CFL 

L2 is regular.

 

answered by Boss (23.3k points)
edited by
0
make start state as final too.
0
Yes it also accept null .
0
Finite automata can not able to do unbounded comparisons , I am confused now, not able to think about this question ,please simplify it!
0
  • At first we take a string which is accepted by dfa . And then compare string 01 and 10 we get equal .

 

0
how L1 is CFL?
0
We can not construct a DFA  for L1.
+1
what is the correct way to analyse such type of questions , The language is regular or CFL?
0
There are Some example which is really tough to find cfl or regular .First time i am  also get canfusd in this question . Only few question are in this type so we note down and remmember it.
0
thanks!
0 votes
Is option d the answer?
answered by Active (1.8k points)

Related questions

0 votes
1 answer
2
asked Aug 7 in Theory of Computation by himgta Active (1.4k points) | 44 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

39,439 questions
46,622 answers
139,360 comments
57,009 users