Register
Filter

Answers by suryaprakash

–1 votes
31
Self doubt in TOC
Suppose in question we are given the language is Turing Recognizable , can I consider it a CFL or Regular?
Suppose in question we are given the language is Turing Recognizable , can I consider it a CFL or Regular?
0 votes
32
Decidability
L= {<G> | G is CFG and G is NOT ambiguous} . L is TM recognizable or not even TM recognizable?
L= {<G | G is CFG and G is NOT ambiguous} .L is TM recognizable or not even TM recognizable?
0 votes
33
Decidability
Equality of two DPDA is decidable or undecidable ?
Equality of two DPDA is decidable or undecidable ?
0 votes
34
Test Series
Explain please. Answer given is D
Explain please. Answer given is D
0 votes
37
decidable problem
Let L be a DCFL and R is a regular language. Consider the below given problems. P: Is L=R ? Q: Is R ⊆L ? Discuss decidablity of P and Q.
Let L be a DCFL and R is a regular language. Consider the below given problems.P: Is L=R ?Q: Is R ⊆L ?Discuss decidablity of P and Q.
1 votes
38
decidability
Is the following problem decidable-: 1. Given a deterministic context-free grammar G, is L(G) = Σ* for some alphabet Σ ? Please also provide explaination.
Is the following problem decidable-:1. Given a deterministic context-free grammar G, is L(G) = Σ* for some alphabet Σ ?Please also provide explaination.
0 votes
39
Decidability
L={R | R is a regular expression, with atleast one w belongs to L(R), i.e. 101 is substring of w} Which one true? a)L is decidable b) L is undecidable c)L is partially decidable
L={R | R is a regular expression, with atleast one w belongs to L(R), i.e. 101 is substring of w}Which one true?a)L is decidableb) L is undecidablec)L is partially decida...
0 votes
40
what type of language
{$<M>\mid M$ is a $TM$ that doesn't accept any even number} what type of language is it? Recursively enumerable Recursive Not recursively enumerable none of the above
{$<M>\mid M$ is a $TM$ that doesn't accept any even number}what type of language is it?Recursively enumerableRecursiveNot recursively enumerablenone of the above
0 votes
42
GATE IT 2006 | Question: 5
Which regular expression best describes the language accepted by the non-deterministic automaton below? $(a + b)^* \ a(a + b)b$ $(abb)^*$ $(a + b)^* \ a(a + b)^* \ b(a + b)^*$ $(a + b)^*$
Which regular expression best describes the language accepted by the non-deterministic automaton below?$(a + b)^* \ a(a + b)b$$(abb)^*$$(a + b)^* \ a(a + b)^* \ b(a + b)^...
0 votes
43
GATE CSE 1991 | Question: 17,a
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.
0 votes
47
Regular Expressions
$L_1=\{a^nb^m\mid n\geq 3,m\leq 4\}$ Find complement of $L_1.$
$L_1=\{a^nb^m\mid n\geq 3,m\leq 4\}$Find complement of $L_1.$
0 votes
49
Automata Grammar Language
What is the relationship between a Language -to- Grammar and a Grammar -to -Language .Give an example for both. A. One -to- Many B. One -to- One C. Many -to- One D. Many to- Many
What is the relationship between a Language -to- Grammar and a Grammar -to -Language .Give an example for both.A. One -to- ManyB. One -to- OneC. Many -to- One D. Many to-...
0 votes
50
ISRO2011-43
Which variable does not drive a terminal string in grammar? $S \rightarrow AB$ $A \rightarrow a$ $B \rightarrow b$ $B \rightarrow C$ A B C S
Which variable does not drive a terminal string in grammar?$S \rightarrow AB$$A \rightarrow a$$B \rightarrow b$$B \rightarrow C$ABCS
0 votes
51
ISRO2016-38
What is the highest type number that can be assigned to the following grammar? $S\to Aa,A\to Ba,B \to abc$ Type 0 Type 1 Type 2 Type 3
What is the highest type number that can be assigned to the following grammar?$$S\to Aa,A\to Ba,B \to abc$$Type 0Type 1Type 2Type 3
1 votes
53
Peter Linz Exercise 5.1
Is the following language context-free? L= { uvwvR : u,v,w∈ {a,b}+ |u| = |w| =2 } If yes, provide set of productions for the same.
Is the following language context-free?L= { uvwvR : u,v,w∈ {a,b}+ |u| = |w| =2 }If yes, provide set of productions for the same.
0 votes
56
theory of computation
I guess the Language , L = { } ...please verify ...
I guess the Language , L = { } ...please verify ...
0 votes
60
#TOC what will be the R.E of this DFA?
I'm getting R.E as 0*1(01)*1(0+1)* but people are getting (0+10)*11(1+0)* Please tell, how!?
I'm getting R.E as 0*1(01)*1(0+1)* but people are getting (0+10)*11(1+0)*Please tell, how!?
Page: