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

in Theory of Computation by Junior (545 points)
retagged by | 297 views

2 Answers

+4 votes
Best answer

L2 is dcfl and L1 is Cfl
soln for L2  Let E = { aib | i ≠ j and 2i ≠ j }
Split it as unions of  3 languages.

{ aibj | i > j } ∪ { aibj | i < j and 2i > j } ∪ { aibj | 2i < j }

G1 = { aibj | i > j }

G2 = { aibj | i < j and 2i > j }

G3 = { aibj | 2i < j }

G1 and G3 are quite easy to figure out. 
for G1
S →   aSb | aS1
S→ aS1 |ε

for G3
S → aSbb | S1b
S1 → S1b | ε 

Now tricky part is G2.
S → aSb | aS1b
S1 → aS1bb | aS2bb
S2 → ε

note- L2 is  given as problem 2.24 in shipser book.

by Boss (12.3k points)
selected by
+5 votes


why ? because  two comparison at a time which is not possible with a stack so its csl if it were written as
M!=n OR M!=2n then it will be CFL .

L2 is DCFL so CFL also 

why ? because we can accept every string in l2 language deterministically push a's into stack when b's comes start poping it aftet that accept it.

so A) option true .

by Boss (19.9k points)
edited by

In L1 : {ab | m< n or m>n } and { ab| m <2n or m>2n }

Here and is nothing but intersection in two sets :

m<n intersection m<2n gives --> m<n 

m>n intersection m>2n gives --> m>=2n

So L1 : {ab | m<n or m>=2n } ---> Hence Language is NCFL.

So option B is correct.


@Gate Mission 1

According to u we can rewrithe L1 : {ab | m<n or m>=2n } 

but check string aabbb is not accepting in ur language while it is accepting in given L1 in question.

n=2 m=3

3<2 or 3>=4 (both are false) // so ur language wont accept

@Rajesh Pradhan. thanks for example.

Agreed i gave wrong language. Can you tell me where did i messed up in my solution ?
@kunal chalotra plz explain about L1

Q1. if it is csl then plz explain how we accept this using 2 stack. (I know it is possible but i m not getting the procedure right now)

Q2."if were written as  m!=n OR m!=2n then it will be CFL " how this possible using single stack.

Thanks in advance.
@rajesh  bro .acc to gate point of view i have solved previous year with basics identification properties only .the thing which u r asking i myself don't know :( how it will be actually be done  using two stacks.

for q2 : for making NPDA of m!=n OR m!=2n, at every step of the transition we will have two copies  one for PUSH and one for POP with this way we will be able to accept the string non deterministically making its cfl .


for q2 : for making NPDA of m!=n OR m!=2n  (I think it should be DPDA instead of NPDA)

first, we have to push all a's into the stack and when b arrives pop a for each arrival of b 

case 1:- if b still coming while stack is empty (all a poped) THEN m!=n Condition True and we wont check m!=2n.

case 2:- if b over and at the same time the stack is empty means m=n (Now here imp. point is if m=n then m!=2n is always true so no need to check m!=2n)

Note:- My point is we never going to check here m!=2n condition So we can find here deterministically by just checking no of a's are equal to no. of b's or not which makes it DPDA.

Finally, {ab | m!=n or m!=2n } is equvalent to {ab | m!=n } is eqivalent to {ab | m< n or m>n } which can be realized using DPDA.

plz correct me!!! 

Related questions

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
50,288 questions
55,719 answers
90,125 users