network 200.20.11.144/27 , Which of the following languages are context free

Question

In the network 200.20.11.144/27, the fourth octet (in decimal) of the last IP address of the network which can be assigned to a host is____

Which of the following languages are context free?

• A. $L_1=\{a^mb^na^nb^m \mid m,n \geq 1\}$
• B. $L_2=\{a^mb^na^mb^m \mid m,n \geq 1\}$
• C. $L_3=\{a^mb^n \mid m= 2n+1\}$

Comments

ok sir thanks and regard and please verify the soln of q49  and is there any simpler way to find CFG,CFL

---

something that can be implement by PDA or using 1 stack .

L1: push a's, push b's, read a's pop b's , read b's pop a's , Yes 

L2:

a)  Push a's, read b and donothing , read a's and pop's a's from stack, then there is nothing in stack to match with remaining b's in input.

 or 

b) Push a's , push b's , read a's and do nothing , read b's and pop b's from stack, there is nothing in input to match with remaining a's in stack .

so L2 is not CFL 

L3: Donothing for only 1 a ,  after that push 1 a and donothing 1 a, keep doing  it in cycle, so that n a's we have in stack, read b's and pop a's. L3 is CFL 

---

in short if power of a and b are different they are CFL else not CFL

Answer 1

mask is 27 so last 5 bit will be host bits here

200.20.11.144=200.20.11.10010000/27

Lowest Address=200.20.11.100 00000/27=200.20.11.128/27

Highest Address=200.20.11.100 11111/27=200.20.11.159/27

Here, Subnet id=200.20.11.128/27

       Direct Broadcasting address=200.20.11.159/27

so last address to give to host is 200.20.11.158/27

Answer 2

Q49 L1 and L3 are Context Free 

L1 is a^mbⁿaⁿb^m ,here in one stack we will push first m a's then push n b's,then for each pop of 'b' print 'a' and each pop of 'a' print 'b', so only one stack is required, so CFL

L2 is a^mbⁿa^mb^n,, here two stacks will be required one stack will not be sufficient for comparison, say we have push first m a's then n b's in stack,then how to print m a's ? so 2 stacks will be required here.So not CFL

L1 is a^mbⁿ,m=2n+1, is equivalent to a²ⁿ⁺¹bⁿ ,only one comparison so CFL