Recent questions and answers in Theory of Computation - GATE CSE Doubts

0 votes

0 answers

made easy test series DPDA doubt

asked 12 hours ago in Theory of Computation by Dheeraj Varma (13 points) | 5 views

0 votes

0 answers

made easy test series DPDA doubt
Why II. is invalid??

asked 12 hours ago in Theory of Computation by Dheeraj Varma (13 points) | 4 views

0 votes

0 answers

Toc : Undecidability Ace test series

asked 16 hours ago in Theory of Computation by Chirag Shilwant (167 points) | 18 views

0 votes

2 answers

Made Easy Test (TOC)

answered 18 hours ago in Theory of Computation by Deepakk Poonia (Dee) (677 points) | 42 views

0 votes

0 answers

GATE GURU: TURING MACHINES

asked 18 hours ago in Theory of Computation by Debapaul (642 points) | 23 views

0 votes

0 answers

Gate 1992 Question
In which of the cases stated below is the following statement true? “For every non-deterministic machine M1, there exists an equivalent deterministic machine M2 recognizing the same language“. (a) M1 is a non-deterministic finite automaton (b) M1 is a non-deterministic PDA (c) M1 is a non-deterministic Turing machine (d) For no machine M1 use the above statement true

asked 2 days ago in Theory of Computation by veenaskumar (7 points) | 3 views

0 votes

0 answers

GATE 2015 Question
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement? (A) Q1 is in NP, Q2 in NP-hard (B) Q2 is in NP, Q1 is NP-hard (C) Both Q1 and Q2 are in NP (D) Both Q1 and Q2 are NP-hard

asked 2 days ago in Theory of Computation by veenaskumar (7 points) | 2 views

0 votes

0 answers

Identifying classes of languages self doubt
I was reading this link https://gatecse.in/identify-the-class-of-a-given-language and I came up with a few doubts. 5. L={wxw∣w,x∈(a+b)∗} Suppose w=101 and x=0 and I give the machine 1010101. It should and it is accepting it. But if I ... . L={xww∣w,x∈(a+b)∗} Suppose x=epsilon w=101. It should and it is accepting 101101. But why is it not rejecting 1011?

asked 3 days ago in Theory of Computation by DukeThunders (409 points) | 4 views

0 votes

0 answers

Self Doubts #Decidablity
I am looking the explanation of the below mentioned being decidable / Undecidable. (Given : Defination of TM in binary) Turing machine's control head move left/ right once, for a given input . Turing machine's control head move left/ right any ... answer vary from 2nd point ?) Turing machine replaces at least one character / exactly k (finite) characters in the input.

asked 3 days ago in Theory of Computation by dr_Jackal (16 points) | 4 views

0 votes

0 answers

Self Doubt #regular languages
What is PHI in Finite Machine representation, is it an isloated state ? , and how come the below is true ∅ ∗ = epsilon

asked 3 days ago in Theory of Computation by dr_Jackal (16 points) | 4 views

0 votes

1 answer

TOC : ACE TEST SERIES

answered 3 days ago in Theory of Computation by kalra05 (46 points) | 10 views

0 votes

0 answers

TOC Ace test series

asked 3 days ago in Theory of Computation by Chirag Shilwant (167 points) | 5 views

0 votes

0 answers

Self Doubt : TOC
Q. REL(which is REC) $\cup$ REL(which is not REC) =?

asked 3 days ago in Theory of Computation by Chirag Shilwant (167 points) | 6 views

0 votes

0 answers

GATE MOCK TEST 3 GATE 2019 – REPORTS

asked 4 days ago in Theory of Computation by DukeThunders (409 points) | 8 views

0 votes

0 answers

#MadeEasyTOC
Someone plz explain I option Answer given is II and III are cfg. If (a^x)(b^y) | x=y^2 then will it be cfg??

asked 4 days ago in Theory of Computation by nandani17 (29 points) | 9 views

0 votes

0 answers

ME CBT How is "A" regular?

asked 5 days ago in Theory of Computation by toxicdesire (223 points) | 28 views

0 votes

0 answers

Ace Mock Test Full length
Doubt: 1) what happens when input is ‘a’ and top of the stack is ‘a’? 2) How C can be the answer and not D?

asked 5 days ago in Theory of Computation by Rudr Pawan (731 points) | 17 views

0 votes

0 answers

applied gate:TOC

asked 5 days ago in Theory of Computation by abhinav649 (65 points) | 46 views

0 votes

0 answers

self doubt on theory of computation
Let L1 is CFL but not regular and L2 is regular .£ ={a,b}. L1 intersection L2 is empty . Can we say L1 union L2 is CFL but not regular(always)?? in this L1 is the left one and L2 is right one I am getting confused that isn't L3 = a^ib^jc^k i,j,k>=0 and all independent whih makes L3 regular

asked 5 days ago in Theory of Computation by Rajat Maheshwari (10 points) | 23 views

0 votes

1 answer

Consider L = {a^n b^n c^n |n ≥ 0}. Is L'(L Complement) a CFL? Prove it.

answered 6 days ago in Theory of Computation by shashin (1.3k points) | 18 views

0 votes

0 answers

Toc on Languages
Can anybody answer with an explanation?

asked Jan 15 in Theory of Computation by kashyap02 (12 points) | 20 views

0 votes

2 answers

ACE Test Series Test 26 Q25 TOC
They have given that both are correct but how is it so? There are some CFL which are inherently ambiguous. So how can there exist an unambi grammar for such languages?

answered Jan 14 in Theory of Computation by blackcloud (55 points) | 74 views

0 votes

0 answers

Self Doubt: Friend Send
Ans should be both false right? My logic For the first one say $S=\phi$ then $\phi^*=\epsilon$ which is finite only and for the second one $S=a$ then $(a)^*$ countably infinite right?

asked Jan 13 in Theory of Computation by Debapaul (642 points) | 22 views

0 votes

0 answers

theory of computation regular expression.
Identify from the list below the regular expression that generates all and only the strings over alphabet {0,1} that end in 1. (0*1*)+1 (0+1)*1+1 (0*+1)+ (0*1)

asked Jan 13 in Theory of Computation by Abhishek Singh Arya (6 points) | 21 views

0 votes

0 answers

UGCNET_DEC-2019

asked Jan 13 in Theory of Computation by Lakshmikanta (12 points) | 3 views

0 votes

0 answers

ISRO 2020 Recruitment for Scientist - BE-003
Which of the following classes of languages can validate an IPv4 address in dotted decimal format? It is to be ensured that the decimal values lie between 0 and 255? (a) RE and Higher (b) CFG and Higher (c)CSG and Higher (d)Recursively enumerable language

asked Jan 12 in Theory of Computation by Debjit0007 (6 points) | 18 views

0 votes

1 answer

ace test series toc cfl rel
Q.

answered Jan 11 in Theory of Computation by shashin (1.3k points) | 15 views

+3 votes

0 answers

MADE EASY SELF DOUBT : AUTOMATA
Consider the following languages $L_1$ and $L_2$ $L_1=\{a^mb^n|m,n \ge$ 0\}$ $L_2=\{a^mb^n|m=n\}$ if $(L_1 \cup \overline{L_2})=L$, then what is the language $L?$

asked Jan 10 in Theory of Computation by Debapaul (642 points) | 42 views

0 votes

2 answers

Made Easy Mock 1
Their reasoning for III does not seem correct. Non determinism comes in a PDA when we have more than one move on the same combination of stack top and input character, which is not the case here. I think it’s incorrect because in III b) we cannot push 11. Correct me if I’m wrong.

answered Jan 9 in Theory of Computation by Mk Utkarsh (472 points) | 61 views

0 votes

0 answers

testbook full test
The finite state automata represents a)complements a given bit pattern b)find 2’s complement of a given bit pattern c)increases a given pattern by 1 d)change the sign bit.

asked Jan 8 in Theory of Computation by abhinav649 (65 points) | 14 views

0 votes

0 answers

testbook full length
The finite state automata represents a)complements a given bit pattern b)find 2’s complement of a given bit pattern c)increases a given pattern by 1 d)change the sign bit. [closed]

asked Jan 8 in Theory of Computation by abhinav649 (65 points) | 14 views

0 votes

0 answers

#toc#undecidability
A NOT RE language is countable but Set of non-RE Language is not countable? True or false. If true how a non re language is countable and then it should be R.E as its has enumeration procedure!

asked Jan 7 in Theory of Computation by kalra05 (46 points) | 26 views

0 votes

1 answer

Class of given language
Is the language $L = \{a^m b^n | m +n = p \}$ a CFL? Nothing is mentioned in the question, so I just assumed that m,n,p >= 0.

answered Jan 7 in Theory of Computation by shashin (1.3k points) | 27 views

0 votes

1 answer

GATEFORUM AUTOMATA AMBIGUITY

answered Jan 7 in Theory of Computation by Deepakk Poonia (Dee) (677 points) | 31 views

0 votes

2 answers

GATE FORUM: AUTOMATA
Ans given is $C$ , but how can it be so? there are some languages which are accepted by $\epsilon - NFA$ which will not be recognized by a normal NFA untill and unless it is converted, so how is $S1$ correct? And there are some regular languages ... S1: A language is regular if there exists an NFA that accepts it S2: A language is regular if there exists a DFA that accepts it

answered Jan 7 in Theory of Computation by Vimal Patel (852 points) | 28 views

0 votes

0 answers

MADE EASY TEST SERIES CFL
Which of the following languages is CFL? (a) ${{a^{m}b^{n}c^{n} | m != n}}$ (b) ${a^{m}b^{n}c^{k} | if (m==n) then (n!=k) }$ (C) ${a^{m}b^{n}c^{k} | (m>n) or (n<k) }$ (d) None of the above [closed]

asked Jan 7 in Theory of Computation by tamaldeepmaity (16 points) | 36 views

0 votes

0 answers

GATE GURU TEST SERIES AUTOMATA
Let $A$ be a $regular$ $language$ and $B$ be a $CFL$ over the alphabet $\sum^*$, which of the following about the langauge $R=\overline{A}-B$ is $TRUE?$ R is necessarily $CFL$ but $not$ necessarily $regular$ R is necessarily $regular$ but $infinite$ $R$ is ... then $\overline{A}-B=a^xb^y$, where $x\neq y$, so it is a $CFL$ right? So option $a$ should be correct right?

asked Jan 6 in Theory of Computation by Debapaul (642 points) | 33 views

0 votes

1 answer

SINGLE SUBJECT : THEORY OF COMPUTATION - Q2
Let L = $\{\text{Language of CFG's that are ambiguous} \}.$ Let $\text{L}$' be a compliment of language L. Which of the following is true? $\text{L is RE and L' is RE}$ $\text{L is not RE and L' is RE}$ ... has an ambiguous grammar. Hence every CFL which is non-empty will be in $L$. So L is a set of all non-empty CFL's. How to proceed?

answered Jan 5 in Theory of Computation by srestha (636 points) | 36 views

0 votes

0 answers

MadeEasyFULL SYLLABUS TEST-5 (ADVANCE LEVEL) GATE 2020 Q55 DFA

asked Jan 5 in Theory of Computation by DukeThunders (409 points) | 15 views

0 votes

0 answers

appliedcourse gate
Please explain with reasons.

asked Jan 5 in Theory of Computation by chandrikabhuyan8 (120 points) | 26 views

To see more, click for all the questions in this category.

Recent questions and answers in Theory of Computation

3,089 questions

1,539 answers

9,246 comments

89,827 users