Recent activity by asterixbachman / GATE Overflow for GATE CSE

2 answers

1

Turing Recognizable and Turing Decidable
Caption Can someone give a clear explanation to this answer?

CaptionCan someone give a clear explanation to this answer?

722 views

commented Jan 27, 2017

2 answers

2

question
Which of the following statements is/are true about the automata? (i) DFA is more efficient but less powerful than NFA (ii) DPDA is more powerful but less efficient than NPDA (iii) DTM is more efficient but less powerful than NTM (a) (i), (ii) & (iii) (b) Only (i) & (ii) (c) Only (ii) & (iii) (d) Only (i) & (iii)

Which of the following statements is/are true about the automata?(i) DFA is more efficient but less powerful than NFA(ii) DPDA is more powerful but less efficient than NP...

8.6k views

answer reshown Jan 20, 2017

2 answers

3

Self doubt
Can we say Recursive languages are Turing Recognizable? As they are decidable, so they are recognisable also.

Can we say Recursive languages are Turing Recognizable?As they are decidable, so they are recognisable also.

357 views

answered Jan 20, 2017

1 answer

4

Interesting Problem of TOC Test Series
Which of following Is closed under Homomorphism? A. Computable Enumerable Language B. Decidable Language C. DCFL D. CSL Explain Neatly.

Which of following Is closed under Homomorphism?A. Computable Enumerable LanguageB. Decidable LanguageC. DCFLD. CSL Explain Neatly.

303 views

answered Jan 20, 2017

2 answers

5

COMPLEMENT OF CSL

1.0k views

commented Jan 17, 2017

1 answer

6

#finding out regular expression for given regular language
I am finding very difficulty to find out regular expression for given regular language. Kindly explain me the entire procedure to get the correct answer in minimum tume. Thanks & Regards, Kiran Watts

I am finding very difficulty to find out regular expression for given regular language. Kindly explain me the entire procedure to get the correct answer in minimum tume.T...

499 views

comment reshown Jan 17, 2017

1 answer

7

L = { 0n+m 1n+m 0m | n, m >= 0 } CSL or RE?
$L = \{ 0^{n+m }1^{n+m} 0^m \mid n, m \geq 0 \}$ The above language is (a) CFL but not Regular (b) CSL but not CFL (c) RE but not CSL (d) None of the above I thought the answer would be (b) CSL but not CFL but it was given as (c) RE but not CSL Can anyone explain how?

$L = \{ 0^{n+m }1^{n+m} 0^m \mid n, m \geq 0 \}$The above language is (a) CFL but not Regular(b) CSL but not CFL(c) RE but not CSL(d) None of the aboveI thought the answe...

2.8k views

answer selected Jan 17, 2017

3 answers

8

UGC NET CSE | June 2016 | Part 3 | Question: 23
The regular expression for the complement of the language $L=\{a^nb^m \mid n \geq 4, m \leq 3\}$ is: $(\lambda +a+aa+aaa)b^*+a^*bbbb^*+(a+b)^*ba(a+b)^*$ $(\lambda +a+aa+aaa)b^*+a^*bbbbb^*+(a+b)^*ab(a+b)^*$ $(\lambda +a+aa+aaa)+a^*bbbbb^*+(a+b)^*ab(a+b)^*$ $(\lambda +a+aa+aaa)b^*+a^*bbbbb^*+(a+b)^*ba(a+b)^*$

The regular expression for the complement of the language $L=\{a^nb^m \mid n \geq 4, m \leq 3\}$ is:$(\lambda +a+aa+aaa)b^*+a^*bbbb^*+(a+b)^*ba(a+b)^*$$(\lambda +a+aa+aaa...

4.1k views

commented Jan 16, 2017

2 answers

9

Doubt in GateCse Decidability Blog
In the deciadability chart mentioned on http://gatecse.in/grammar-decidable-and-undecidable-problems/ The undecidable problems mentioned here are semidecidable(RE but not REC) not NOT RE.Or there is no such relation? Can someone have a look and tell please?

In the deciadability chart mentioned on http://gatecse.in/grammar-decidable-and-undecidable-problems/The undecidable problems mentioned here are semidecidable(RE but not ...

758 views

answered Jan 15, 2017

1 answer

10

Plz explain
. Consider these 2 statements: S1: LR = L, if and only if L is the language of palindromes. where LR is obtained by reversing all the strings of L. S2: | L1∙ L2 | = | L1 | × | L2 | Relation? (a) Both are F (b) Both are T 2 (c) S1 → T, S2 → F (d) S1 → F, S2 → T

. Consider these 2 statements:S1: LR = L, if and only if L is the language of palindromes. where LR is obtained by reversing all the strings of L.S2: | L1∙ L2 | = | L1 ...

1.5k views

commented Jan 12, 2017

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