Register

ISRO-DEC2017-24

• recategorized by
1,328 views
4 votes
4 votes

Let $L_1$ be regular language, $L_2$ be a deterministic context free language and $L_3$
a recursively enumerable language, but not recursive. Which one of the follewing statements is false ?

  1. $L_3\cap L_1$ is recursive
  2. $L_1\cap L_2\cap L_3$ is recursively enumerable
  3. $L_1\cup L_2$ is context free
  4. $L_1\cap L_2$ is context free
• recategorized by
User Avatar

1 Answer

Best answer
12 votes
12 votes
$L_3\cap L_1$  = $RE\cap Regular  $ = RE but not REC

$L_1\cap L_2\cap L_3$ = $Reg\cap DCFL\cap RE$ = RE

$L_1\cup L_2$  = $Reg \cup DCFL$= DCFL hence CFL also

$L_1\cap L_2$ = $Reg\cap DCFL$ = DCFL hence CFL also

A is answer
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

5 votes
5 votes
2 answers
1
gatecse asked Dec 17, 2017
1,217 views
ISRO-DEC2017-26
Which of the following are context-free? $A=\{a^n b^n\, a^mb^m\mid m,n\geq0\}$ $B=\{a^m b^n\, a^mb^n\mid m,n\geq0\}$ $C=\{a^mb^n\mid m\neq 2n,\,m,n\geq0\}$ A and B only A and C only B and C only C only
Which of the following are context-free?$A=\{a^n b^n\, a^mb^m\mid m,n\geq0\}$$B=\{a^m b^n\, a^mb^n\mid m,n\geq0\}$$C=\{a^mb^n\mid m\neq 2n,\,m,n\geq0\}$A and B only A and...
User Avatar
1 votes
1 votes
1 answer
2
gatecse asked Dec 17, 2017
1,041 views
ISRO-DEC2017-25
Let $L=\{a^p\mid p \text{ is a prime}\}.$ Then which of the following is true It is not accepted by a Turing Machine It is regular but not context-free It is context-free but not regular It is neither regular nor context-free ,but accepted by a Turing Machine
Let $L=\{a^p\mid p \text{ is a prime}\}.$ Then which of the following is trueIt is not accepted by a Turing MachineIt is regular but not context-freeIt is context-free b...
User Avatar
3 votes
3 votes
2 answers
3
gatecse asked Dec 17, 2017
2,030 views
ISRO-DEC2017-23
Identify the language generated by the following grammar $S\rightarrow AB\\ A\rightarrow aAb\mid \varepsilon\\ B\rightarrow bB\mid b$ $\{a^m b^n\mid n\geq m,m>0\}$ $\{a^m b^n\mid n\geq m,m\geq0\}$ $\{a^m b^n\mid n> m,m>0\}$ $\{a^m b^m\mid n> m,m\geq0\}$
Identify the language generated by the following grammar$S\rightarrow AB\\ A\rightarrow aAb\mid \varepsilon\\ B\rightarrow bB\mid b$$\{a^m b^n\mid n\geq m,m>0\}$ $\{a^m b...
User Avatar
4 votes
4 votes
2 answers
4
gatecse asked Dec 17, 2017
3,432 views
ISRO-DEC2017-22
Consider the grammar with productions $S\rightarrow aSb\mid SS \mid \varepsilon$ This grammar is not context-free, not linear not context-free, linear context-free, not linear context-free, linear
Consider the grammar with productions$S\rightarrow aSb\mid SS \mid \varepsilon$This grammar is not context-free, not linearnot context-free, linearcontext-free, not linea...
User Avatar
Link Copied!