Log In
3 votes

Choose the correct statement -

  1. $A=\{a^nb^n \mid n= 1, 2, 3, \ldots\}$ is a regular language
  2. The set $B$, consisting of all strings made up of only $a's$ and $b's$ having equal number of $a's$ and $bs$ defines a regular language
  3. $L(A^*B)\cap B$ gives the set $A$
  4. None of the above
in Theory of Computation
recategorized by

3 Answers

7 votes
Best answer

option d  is right.

  • $^{a^nb^n}$ is DCFL but not reguler. so option a is false.
  • equal no of a's and equal no of b's is also DCFL but  not reguler.option b is false.
  •  L(A*B)$\cap$ B gives the set B. SO OPTION c is also false.

selected by
6 votes

(a) A={anbn| n=1,2..} is DCFL .So,(a) is False

(b)The set B,consisting of all strings made up of only a's and b's having equal number of a's and b's is a DCFL. So,(b) is False.

(c) L(A*B) $\cap$ B

A= {anbn| n=1,2..}

B=consisting of all strings made up of only a's and b's having equal number of a's and b's

L(A*B)= L( { B + AB + AAB + ...} )

Now, L(A*B) $\cap$ B = B

So,(c) is False.

Ans:(d) None of the above

edited by
* represents kleane closure not concatenation answer is still d

@VS Here A,B defined as in the option then why you have  taken random definition?

Option C is incorrect.

Here A=a`nb`n  B=equal no. of a's and b's 

On Expanding L(A*B)=L({B+AB+AAB+ ...})

Now on Taking Intersection with B results leads to SET B.

In my opinion Cfl intersection Cfl is not closed hence the resultant language belongs to Csl so answer is may be A or May be B but not a particular set . If i I am wrong rectify me

 L(A*B) ∩ B = B

 This would have been correct logic and thinking Since He hasn't mentioned what is A and B (Though from the Questions, It seems His intension was that We assume A and B as the language Set described in the Option 1 and 2 respectively)..But If You say that  L(A*B) ∩ B = B, then You have self-assumed that A and B are some Random Regular expressions or Symbols in some alphabet...But even then, It is wrong. Because we can't intersect a Language with a Regular expression (Though People do because of "Without loss of generality")..Thus the expression must have been either

 (A*B) ∩ B = B with Intersection operation defined on REs


 L(A*B) ∩ L(B) = L(B)

So, It is clearly some Printing mistake or Not properly framed question. And It is now "The Interpretation Game"..

People Interpret what they interpret.

–1 vote
C Correct

i think option none

Related questions

3 votes
3 answers
$CFG$ (Context Free Grammar) is not closed under: Union Complementation Kleene star Product
asked Apr 22, 2018 in Theory of Computation Arjun 793 views
4 votes
2 answers
The $FSM$ (Finite State Machine) machine pictured in the figure above Complements a given bit pattern Finds $2's$ complement of a given bit pattern Increments a given bit pattern by $1$ Changes the sign bit
asked Apr 22, 2018 in Theory of Computation Arjun 3.6k views
2 votes
3 answers
A $CFG$ (Context Free Grammar) is said to be in Chomsky Normal Form $(CNF)$, if all the productions are of the form A$\to$ BC or A$\to$ a. Let $G$ be a $CFG$ in $CNF$. To derive a string of terminals of length x, the number of products to be used is: $2x-1$ $2x$ $2x+1$ $2^{x}$
asked Apr 22, 2018 in Theory of Computation Arjun 1.7k views
3 votes
2 answers
A particular BNF definition for a "word is given by the following rules. <word> :: =<letter> I <letter> <charpair> I <letter><intpair> <charpair> :: =<letter><letter> I <charpair><letter><letter> <intpair> :: = <integer><integer> I <intpair><integer><integer> <letter> ... lexical entries can be derived from < word >? pick picks c44 I, II and III I and II only I and III only II and III only
asked Apr 22, 2018 in Theory of Computation Arjun 1.9k views