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

0 votes

1 answer

Context Free Language
Is this CFL? L = {wcwr | w, c ϵ {0,1}+ and |c| = 2}

answered 7 hours ago in Theory of Computation by RavGopal (48 points) | 9 views

0 votes

0 answers

Decidability In TOC
Turing Machine accepts a regurlar language. Is it decidable or not ?

asked 3 days ago in Theory of Computation by ajaybhardwaj1999 (6 points) | 9 views

+1 vote

1 answer

pushdown automata #CFL
Is the following language context-free language(CFL) or not? If yes, then is it Deterministic-CFL (DCFL)? L={ $a^i b^j$ where $i\neq 2*j+1$ and $j \geq 1$ and $i\geq 1$ }

answered 3 days ago in Theory of Computation by RavGopal (48 points) | 29 views

0 votes

1 answer

Made easy Theory book
Is $a ^{n} b^{2n} c^{ 3n}$ such that $n >0$ context free or not ? full explanation please.

answered 5 days ago in Theory of Computation by premu (69 points) | 15 views

0 votes

0 answers

Show that the language L = w1cw2 : w1, w2 ∈ {a, b}+ , {w1 ≠ w^R2 } with Σ = {a, b, c}, is context-free.

asked 5 days ago in Theory of Computation by roh (17 points) | 10 views

0 votes

0 answers

In Compiler Construction course While mapping the conditions for the Shift and Reduce actions in SLR table

asked 6 days ago in Theory of Computation by Arsalan Sheikh (6 points) | 11 views

0 votes

1 answer

Regular expression self doubt
Given is a Regular Expression, 0*(10*)* If we want ot generate strings from this regular language , then while generating a string do we need to keep value of * same for a string or can we change it for every digit in the regular expression. For eg- ... 0^4(1 0^3)^6 in a string . Please answer this since, I am finding it difficult to solve these type of questions.

answered Jun 23 in Theory of Computation by Nikhil_dhama (87 points) | 14 views

0 votes

0 answers

MINIMUM FINITE STATE MACHINE
Is it true that if we reverse the DFA twice and delete unreachable states in every step then we definitely get the minimum DFA always? i.e., DFA --> REVERSE OF DFA AND REMOVE UNREACHABLE STATES --> CONVERT IT INTO DFA HERE IT IS THE REVERSAL OF THE ... DOUBT IS , IS IT THE RESULTANT DFA IS ALWAYS MINIMUM DFA . IF SO , PLEASE GIVE AN IDEA TO AT LEAST CONVINCE ME .

asked Jun 19 in Theory of Computation by NARAYANA (7 points) | 12 views

0 votes

0 answers

PDA construction
How to construct the PDA for the language on alphabet 0,1 which accept all the strings with number of 0's in the string is not equal to the number of 1's in the string ?

asked Jun 17 in Theory of Computation by NARAYANA (7 points) | 4 views

0 votes

0 answers

Peter Linz Exercise-8.2 Context Free Lnaguages
Show that the following language is context free L={$w\epsilon (a, b)$* : $n_{a}(w)=n_{b}(w)$, w does not contain the substring aab}

asked Jun 16 in Theory of Computation by aditi19 (57 points) | 8 views

0 votes

0 answers

gfgpracticecontest
given ans is 3.anyone please minimize this step by step???

asked Jun 11 in Theory of Computation by Papun417 (7 points) | 6 views

0 votes

0 answers

Regular Expression
what is the regular expression for strings of length atmost 2 over {a,b}. Plz give detailed soln.

asked Jun 11 in Theory of Computation by Vaishalikashyap (10 points) | 18 views

0 votes

1 answer

regular expression
Regular expression for all strings starts with a or ending with b?

answered Jun 11 in Theory of Computation by Vaishalikashyap (10 points) | 15 views

0 votes

0 answers

Peter Linz Theory of Computation Exercise 5.1 Question-15

asked Jun 11 in Theory of Computation by aditi19 (57 points) | 10 views

0 votes

0 answers

TOC GATE2013-32 doubt regarding dcfl
$L2 = \left \{ 0^p1^q0^r ∣ p,q,r ≥ 0, p ≠ r \right \}$ Is the above language dcfl? The comments in the question state that it is but what about the case when #1’s = 0. Then how is the first half of 0’s separated from the second half of 0’s deterministically? Ref – https://gateoverflow.in/1543/gate2013-32

asked May 30 in Theory of Computation by abhijit_m (6 points) | 13 views

0 votes

1 answer

TIFR2020-B-2
Consider the following statements . 1. The intersection of two context - free languages is always context - free . 2. The super - set of a context - free language is never regular. 3. The subset of a decidable language is always decidable . 4. Let $\sum$ = { a , b , c } . Let L$\subseteq$ ... ) and ( 3 ) ( d ) Only ( 4 ) ( e ) None of ( 1 ) , ( 2 ) , ( 3 ) , ( 4 ) are true

answered May 26 in Theory of Computation by Kushagra गुप्ता (415 points) | 11 views

0 votes

0 answers

PYQ GATE 2008
What will be the correct option ?

asked May 19 in Theory of Computation by Ananya2000 (22 points) | 8 views

0 votes

0 answers

PYQ GATE CS 2012
What will be the correct option for the above DFA ?

asked May 19 in Theory of Computation by Ananya2000 (22 points) | 5 views

0 votes

1 answer

Self Doubt from notes
What will be the language generated by the following grammar ? S → 0S1S / 1S0S/E P.S. – E is Epsilon

answered May 18 in Theory of Computation by toxicdesire (305 points) | 15 views

+1 vote

0 answers

Theory of computation No of state in dfa
How many three state DFA can be constructed with a designated initial state that accept empty language over the alphabet {a,b}?

asked May 16 in Theory of Computation by Shreya2002 (7 points) | 45 views

0 votes

0 answers

Mealy and moore machine are in syllabus of GATE?
Mealy and moore machine are in syllabus of GATE? Not found in syllabus broucher as well as in previous years questions. If yes, please provide if any question arrived in previous 10 years.

asked May 15 in Theory of Computation by Cser (6 points) | 6 views

0 votes

0 answers

University of Chicago exam for formal Language
I got the following questions in my exam last week but I am not sure about the answers. Here are my answers. Can anyone verify if my answers are right of wrong? false false true true false false false false true false E

asked May 15 in Theory of Computation by rj865200 (6 points) | 7 views

0 votes

1 answer

#Gate 2021#TOC
Which of the following properties of recursive enumerable set is/are recursive enumerable L = Φ L contains at least 5 members L has exactly one member Please explain

answered May 14 in Theory of Computation by shashin (1.9k points) | 18 views

0 votes

0 answers

#Gate 2021#TOC
Assertion reasoning question: Assertion(a) : Let L is recursive enumerable language and problem X is defined as X: Is L=Φ? is not recursively enumerable Reasoning(r): X violates the condition that says. if L is an infinite set in S, a set of recursive enumerable ... r is not the correct reason for a a is true , r is false a is false, r is true Please answer with explanation

asked May 13 in Theory of Computation by sushmitagoswami (14 points) | 7 views

0 votes

0 answers

GATE # 2021 #TOC
Let X be defined as follows: X: Given M an encoding of a Turing Machine. Does M halt on all inputs? Which of the following is true? X is decidable X is undecidable but partially decidable X is undecidable and not even partially decidable X is not a decidable problem Please answer with explaination.

asked May 13 in Theory of Computation by sushmitagoswami (14 points) | 4 views

0 votes

0 answers

#Gate 2021 #TOC
Which if the following is false? L is recursive if and only if it is generated by some TM in canonical order L is recursively enumerable if and only if there exist a TM which generates L is context sensitive if and only if it is generated by some TM in canonical order None of these. Please answer with explanation.

asked May 13 in Theory of Computation by sushmitagoswami (14 points) | 4 views

0 votes

0 answers

l1 = (ab m>0), l2=lamda. then l is which type of language - regular or context?

asked May 13 in Theory of Computation by gunjanmimo (6 points) | 2 views

0 votes

0 answers

Self doubt for Moore Machine
Q – Construct a Moore machine that takes set of strings over {0,1} and produces A as output, if input ends with ‘10’ and produces B as output if it ends with ‘11’ else produces C. Is my Moore Machine correct ?

asked May 12 in Theory of Computation by Ananya2000 (22 points) | 18 views

0 votes

1 answer

self_doubt union of language in toc
What will be the union of L1 U L2 ? L1= {a^n b ^m | n≤m} L2={a^n b^m | n≥m}

answered May 12 in Theory of Computation by srestha (749 points) | 27 views

0 votes

1 answer

Self doubt from a video !
Is the above DFA correct for acceptiing a string that starts and ends with the same symbol ?

answered May 9 in Theory of Computation by Kushagra गुप्ता (415 points) | 19 views

0 votes

0 answers

Self Doubt from a video
Is the following DFA correct for a accepting a string that starts and ends with the same symbol ?

asked May 8 in Theory of Computation by Ananya2000 (22 points) | 4 views

0 votes

0 answers

Self Doubt Turing Machine
Write the implementation level Turing Machine for following language: L={w∈ {a,b}*, w: 2na(w) nb(w) 3na(w)}

asked May 3 in Theory of Computation by jainpawan21 (8 points) | 5 views

0 votes

0 answers

How to design 2 stack pda for language {w|na=nb=nc where w belongs to (a,b,c)*}

asked May 2 in Theory of Computation by iamayush (6 points) | 5 views

0 votes

0 answers

How to construct a deterministic finite automation equivalent to the grammar S->aS|bS|aA, A->bB, B->aC

asked May 1 in Theory of Computation by Sarika lozy (6 points) | 12 views

0 votes

0 answers

SELF DOUBT(TOC-What type of language is this.)
if we have a language like: L={3,9,27,81,273….} what is this ? is this regular,CFL,CSL or recursive or recursively enumerable?

asked Apr 29 in Theory of Computation by Doraemon (115 points) | 7 views

+1 vote

1 answer

GATE2020-CS-51 Video Solution
Consider the following language. $L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$ The minimum number of states in DFA that accepts $L$ is _________

answered Apr 28 in Theory of Computation by amitkhurana512 (187 points) | 15 views

+1 vote

1 answer

GATE2020-CS-8 Video Solution
Consider the following statements. If $L_1 \cup L_2$ is regular, then both $L_1$ and $L_2$ must be regular. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Both Ⅰ and Ⅱ Neither Ⅰ nor Ⅱ

answered Apr 28 in Theory of Computation by amitkhurana512 (187 points) | 6 views

0 votes

0 answers

TOC The R.E L(r) = (a+ b*) U ε. Is the grammar with productions generated over non-terminals {S, A} ambiguous?

asked Apr 27 in Theory of Computation by siddharths067 (7 points) | 9 views

+1 vote

1 answer

GATE2020-CS-32 Video Solution
Consider the following languages. $\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$ ... - free but not regular and $L_2$ is context-free. Neither $L_1$ nor $L_2$ is context- free. $L_1$ context- free but $L_2$ is not context-free.

answered Apr 26 in Theory of Computation by amitkhurana512 (187 points) | 14 views

+1 vote

1 answer

GATE2020-CS-26 Video Solution
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only

answered Apr 26 in Theory of Computation by amitkhurana512 (187 points) | 15 views

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

Recent questions and answers in Theory of Computation

7,525 questions

1,776 answers

10,835 comments

90,464 users