Recent questions and answers in Theory of Computation

0 votes

0 answers

1

Workbook

asked 36 minutes ago in Theory of Computation by Rhythm (35 points) | 1 view

0 votes

0 answers

2

Countability
Can someone tell me if countability topic from toc is still in syllabus of gate 2019 or not

asked 3 hours ago in Theory of Computation by sanket03 (11 points) | 4 views

0 votes

2 answers

3

Automata
https://gateoverflow.in/?qa=blob&qa_blobid=5795855353278664308

answered 14 hours ago in Theory of Computation by Hemanth_13 Loyal (5.4k points) | 46 views

0 votes

1 answer

4

ACE Test Series

answered 15 hours ago in Theory of Computation by aanchal008 (149 points) | 57 views

+12 votes

9 answers

5

GATE2017-2-16
Identify the language generated by the following grammar, where $S$ is the start variable. $ S \rightarrow XY$ $ X \rightarrow aX \mid a$ $ Y \rightarrow aYb \mid \epsilon$ $\{a^mb^n \mid m \geq n, n > 0 \}$ $ \{ a^mb^n \mid m \geq n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n > 0 \}$

answered 17 hours ago in Theory of Computation by Rishi yadav Loyal (7.5k points) | 1.9k views

0 votes

0 answers

6

Rice theorem
1.{<M>| M is a TM accepts any string starting with 1} 2.{<M>| M is TM accept exactly 20 strings} Please guide I don’t know how to apply rice theorem. for 1. Is Tyes = { string starting with 1} Tno = { all strings – strings starting with 1} what is Tyes and Tno here? I only conclude by intution that when we provide strings as input some got into loop and some got accepts .

asked 1 day ago in Theory of Computation by Learner_jai Active (2.2k points) | 30 views

+4 votes

5 answers

7

UGCNET-Dec2012-III-50
Which of the following definitions generates the same Language as $L$, where $L=\{ WW^R \mid W \in \{a, b\}$*$\}$? $S \rightarrow asb \mid bsa \mid \in$ $S \rightarrow asa \mid bsb \mid \in$ $S \rightarrow asa \mid bsa \mid asa \mid bsb \mid \in$ $S \rightarrow asa \mid bsa \mid asa \mid bsb \mid$

answered 1 day ago in Theory of Computation by aanchal008 (149 points) | 735 views

0 votes

1 answer

8

ace test series
Number of equivalence classes w.r.t language, L={(a^n)(b^n)(c^n)| n>=0} is answer:infinity explain why?

answered 1 day ago in Theory of Computation by anjali007 Active (3.3k points) | 42 views

0 votes

1 answer

9

Ace test series

answered 1 day ago in Theory of Computation by talha hashim Active (4.5k points) | 70 views

0 votes

0 answers

10

ace test series
Which of the following is not REL? A) L={ <M> | L(M)=⏀,M is a TM} B) L={ <M> | L(M)≠⏀,M is a TM} C) L={<M,x> | M halts on x} D) L={<M,x> | M accepts x}

asked 1 day ago in Theory of Computation by talha hashim Active (4.5k points) | 37 views

0 votes

0 answers

11

Zeal Theory of Computation module.
Does the statement given below is true? If a language L is recursive enumerable than there does not exits a TM that could accept complement of L but reject L.

asked 1 day ago in Theory of Computation by Ayan21 (103 points) | 20 views

0 votes

1 answer

12

Self doubt
Unrestricted grammar generate Recursive enumerable language. Am i right??

answered 1 day ago in Theory of Computation by rballiwal Junior (761 points) | 27 views

0 votes

1 answer

13

self doubt - Turing Machines
I have doubt in the following question: Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by CFG G. Let L(M) be the language accepted by a turing machine M. Now, I am getting confused over the keyword “accepted”. What should L(M) be considered? Is it REC or RE?

answered 1 day ago in Theory of Computation by rballiwal Junior (761 points) | 22 views

0 votes

1 answer

14

Self Doubt regarding Type 1
L= a*b* Grammar associated with this language is a Type 3 S---> aS/A A--->bA/€ Now we know that Type 1 Grammar is Non Contracting Grammar Here A---> € is a Contracting production And only S---> € is allowed in Type 1 And if a grammar is not type 1 how it can be type 3 ? Please help

answered 1 day ago in Theory of Computation by rballiwal Junior (761 points) | 62 views

0 votes

1 answer

15

Question on P problem
I think answer should be D. they have given wrong answer. Please correct me if I am wrong.

answered 2 days ago in Theory of Computation by rballiwal Junior (761 points) | 20 views

0 votes

1 answer

16

Context free language Question
please provide solution for given quesion.

answered 2 days ago in Theory of Computation by rballiwal Junior (761 points) | 21 views

0 votes

2 answers

17

pushdown automata
What is the difference between DPDA which accept Language by the empty stack and the one which accepts by final state

answered 2 days ago in Theory of Computation by rballiwal Junior (761 points) | 16 views

0 votes

2 answers

18

Halting problem of TM which recognize recursive languages is undecidable?

answered 2 days ago in Theory of Computation by rballiwal Junior (761 points) | 41 views

0 votes

1 answer

19

Turing Machine lecture content stan..
A = { <M,w> | M is a TM that accepts W} what is A’( A complement)? Pls guide : M is a Tm doesn,t accept w, Unable to approach further Source:https://web.stanford.edu/class/archive/cs/cs103/cs103.1134/lectures/20/Small20.pdf

answered 2 days ago in Theory of Computation by rballiwal Junior (761 points) | 26 views

+1 vote

2 answers

20

UGCNET-AUG2016-III-55
Given the following two languages : $L_{1} = {uww^{R} ν | u, v, w \in (a, b)^{+}}$ $L_{2} = {uww^{R} ν | u, ν, w \in (a, b)^{+} , |u| \geq |ν|}$ Which of the following is correct ? $L_{1}$ is regular language and $L_{2}$ ... not regular language and $L_{2}$ is regular language. Both $L_{1}$ and $L_{2}$ are regular languages. Both $L_{1}$ and $L_{2}$ are not regular languages.

answered 2 days ago in Theory of Computation by lekshmisopanam (309 points) | 292 views

0 votes

0 answers

21

Made easy Theory book
According to the given formula above, how many productions should be there ? S-->aAbB A-->aA | a B-->bB | b According to me., it should be 17 but in the book answer is 9, can anyone tell me how? mage widget

asked 3 days ago in Theory of Computation by Jyoti Kumari97 (65 points) | 23 views

0 votes

1 answer

22

Ace Academy Test series

answered 3 days ago in Theory of Computation by Mk Utkarsh Boss (30k points) | 57 views

0 votes

1 answer

23

toc concept
do recursive language is recursively enumerable as well ? true or false

answered 3 days ago in Theory of Computation by manas (29 points) | 25 views

0 votes

0 answers

24

Turing Machine
L = {M | M is a TM and L(M) is infinite} L is Rec/ RE/ Not RE ? [closed]

asked 3 days ago in Theory of Computation by akshayaK Junior (537 points) | 17 views

+13 votes

4 answers

25

GATE2001-2.6
Consider the following languages: $L1=\left\{ww \mid w \in \{a,b\}^*\right\}$ $L2=\left\{ww^R \mid w \in \{a,b\}^*, w^R \text{ is the reverse of w} \right\}$ $L3=\left\{0^{2i} \mid \text{ i is an integer} \right\}$ $L4= \left\{ 0^{i^2} \mid \text{ i is an integer} \right\}$ Which of the languages are regular? Only $L1$ and $L2$ Only $L2, L3$ and $L4$ Only $L3$ and $L4$ Only $L3$

answered 3 days ago in Theory of Computation by Suneel Padala (207 points) | 1.6k views

0 votes

1 answer

26

recursive language
Can a language exist which is undecidable as well as Recursive language ? If yes please give example.

answered 3 days ago in Theory of Computation by rballiwal Junior (761 points) | 83 views

+4 votes

3 answers

27

Question of regular expression
Consider the following regular expressions : (i) ($(a/b)^{*}$ (ii) $(a^{*}/b^{*})^{*}$ (iii) $((\epsilon /a)b^{*})^{*}$ Which of the following statements are correct ? (a) (i) ,(ii) are equal and (ii) , (iii) are not . (b) (i) ,(ii) are equal and (i) ... give me (a)* . Isn't it so ? From (i) ($(a/b)^{*}$ : I can not separate a and b . So , how can they all be equal ?

answered 4 days ago in Theory of Computation by akshayaK Junior (537 points) | 944 views

0 votes

2 answers

28

Minimal DFA
Given following NFA find the minimal equivalent DFA

answered 4 days ago in Theory of Computation by aambazinga Active (2.2k points) | 74 views

0 votes

2 answers

29

Countable set
If power set of natural number is uncountable , and that is why non RE, then how is it possible set of natural number is countable and RE?------give some reason

answered 4 days ago in Theory of Computation by rballiwal Junior (761 points) | 27 views

0 votes

1 answer

30

TOC Which is(are) regular? Please explain 1 and 4.

answered 4 days ago in Theory of Computation by rballiwal Junior (761 points) | 57 views

+1 vote

1 answer

31

Turing Machine-Techtud
If Turing Machine input tape length,restricted to input length, then the language accepted by Turing Machine $A)$ Regular Language $B)$ CFL $C)$ CSL $D)$ None Ans given CSL but I thought it should be regular then what is difference between input restricted and constant size tape? https://gateoverflow.in/26653/gate1991-17-a Plz confirm what is correct?

answered 4 days ago in Theory of Computation by rballiwal Junior (761 points) | 62 views

0 votes

1 answer

32

UGC NET 2016
Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation RM defined by M. As all states are reachable from the start state, RM has _____ equivalence classes. pls give a detailed solution

answered 4 days ago in Theory of Computation by rballiwal Junior (761 points) | 26 views

0 votes

0 answers

33

UGC NET Doubt
https://gateoverflow.in/13365/ugcnet-dec2014-iii-24 i’ve a small doubt in the solution of this question how is (a+b)*ba(a+b)* complement of the given language?

asked 4 days ago in Theory of Computation by aditi19 Active (2.2k points) | 37 views

0 votes

2 answers

34

DFA doubt
DFA in which 01 and 10 have equal number of occurrences

answered 4 days ago in Theory of Computation by rballiwal Junior (761 points) | 102 views

0 votes

1 answer

35

Conversion of NFA to DFA
convert the following NFA to DFA

answered 4 days ago in Theory of Computation by Devwritt Active (3.9k points) | 24 views

+1 vote

0 answers

36

CONVERT CFG TO GNF
S→ AB A→ BS|b B→ SA|a INTO GNF

asked 4 days ago in Theory of Computation by Menon Karthik (41 points) | 35 views

+2 votes

1 answer

37

ME test series DFA states
The number of states in minimal DFA for strings starting with $ab^{2}$ and ending with $b$ over the alphabet $\left \{ a,b \right \}$ is__________. // doubt: minimal string should be $ abb $ right?

answered 4 days ago in Theory of Computation by rballiwal Junior (761 points) | 39 views

0 votes

1 answer

38

ME Test Series
I know compleiment of CSL is CSL so can anyone explain how to solve these type of problems effectively by saving time.

answered 4 days ago in Theory of Computation by rballiwal Junior (761 points) | 61 views

0 votes

2 answers

39

ME Test Series
Can anyone explain?

answered 4 days ago in Theory of Computation by rballiwal Junior (761 points) | 36 views

0 votes

1 answer

40

What is the difference between a*+b* and (a+b)* ?

answered 4 days ago in Theory of Computation by rballiwal Junior (761 points) | 27 views

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

Recent questions and answers in Theory of Computation

Recent Posts

Recent Blog Comments