1 Crore+ students have signed up on EduRev. Have you? 
Over the alphabet , {0,1} consider the language
Which of the following is true about L.
L is regular.
If L1 is context free language and L2 is a regular language which of the following is/are false?
a) L1L2 is not context free
b) L1 ∩ L2 is context free
c) ~L1 is context free
d) ~L2 is regular
Hence,Option (C) is correct.
Let denote the languages generated by the grammar S→ 0S0 I 00.
Which of the following is TRUE?
Language generated by this grammar is L = (00)^+ that is regular but not 0^+
The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as
With only finite positions in stack, we can have only finite configurations and these can also be modeled as states in a finite
automata.
Language is not regular bcoz we need to match count of c's is equal to count of b's + count of a's
and that can implement by PDA
∂(q0,a,^)= (q0,a) [ push a in stack, as per language a comes first]
∂(q0,a,a)= (q0,aa) [push all a's into stack]
∂(q0,b,a) = (q1,ba) [push b in stack, state change to q1 that sure b comes after a]
∂(q1,b,b)=(q1,bb) [push all b's in stack]
∂(q1,c,b) = (q2,^) [ pop one b for one c]
∂(q2,c,b) = (q2,c) [ pop one b's for each c and continue same ]
∂(q2,c,a) = (q3,^) [ pop one a for one c , when there is no more b in stack]
∂(q3,c,a) = (q3,^) [pop one a for each c and continue same]
∂(q3,^,^) = (qf,^) [ if sum of c's is sum of a's and b's then stack will be empty when there is no c in input]
Note :1. state changes make sure b's comes after a and c's comes after b's]
Consider the languages:
and
Which one of the following statements is FALSE?
L1 is CFL [ put a's in stack, and pop a with each b]]
L2 is CFL [put b's in stack and pop b with each c ]
c) is True.
b) is True CFL is closed under Union [ S> S1  S2 where S1 is grammar for L1 and S2 for L2]
CFL is not closed under Intersection, so intersection of two CFLs may or may not be CFL.
Let's examine:
L1 ∩ L2 = { a^{i}b^{i}c^{i} , i>0 } which is Context sensitive but not context free [can't match a's,b's and c's with one stack]
So a) is False
d) is True
Let L be a regular language and M be a contextfree language, both over the alphabet denote the complements of L and M respectively. Which of the following statements about the language
Take L = Σ* then Lc = ∅ and Mc ∪ ∅ = M^{c}.
We know that complement of CFL need not be a CFL as CFL is not closed under complement
So, (A) and (B) are false.
If we take L = ∅ then L^{c} = Σ* and M^{c} ∪ Σ* = Σ* which is regular  (C) is also false.
So, answer (D)
Regular (in fact finite). Since n is finite, we have a finite set of strings satisfying the given conditions.
So, we can easily make a finite automata for those strings.
For denote the decimal value of
Which one of the following statements is true?
L1 = { s∈(0+1)* ∣ d(s) mod 5=2 } is regular having 2 as final state out of {0,1,2,3,4} states as given in example in posted link [in same DFA , final state will be 2 instead of 0 ]
Similarly L2 = { s∈(0+1)* ∣ d(s) mod 7≠4 } is also regular having states {0,1,2,3,4,5,6} and all are final state except 4
L1 ∩ L2 is L (given problem ) is also regular
As regular languages are closed under intersection.
Hence, D is the correct option.
Let L_{1} be a regular language L_{2}, be a deterministic contextfree language and L_{3} a recursively enumerable, but not recursive, language. Which one of the following statements is false?
A. True: DCFL are closed under Intersection with Regular Languages
C. True: L1 is regular hence also CFL and every DCFL is also CFL and All CFL are closed under Union.
D. True: L1 is regular hence also RE; L2 is DCFL hence also RE; RE languages are closed under Intersection
B. False: L1 is recursive hence also decidable, L3 is RE but not Recursive hence it is undecidable. Intersection of Recursive
language and Recursive Enumerable language is Recursive Enumerable language.
62 videos7 docs102 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
62 videos7 docs102 tests









