search
Log In
Quick search syntax
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
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users 2021 Aug 02 - 08
  1. SarathBaswa

    6 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021

Recent questions and answers in Theory of Computation

0 votes
1 answer 5 views
Is S--> AccB A-->aA/a B-->bB/a a regular grammar according to the type 3 grammar rule i.e, production must be in the form S-->Ax or S-->xA where A is non terminal and x is terminal?
answered 1 day ago in Theory of Computation asqwer 633 points 5 views
0 votes
1 answer 19 views
This question appeared in my b.tech university exam 2021. This question is of 2 marks. As, i’m preparing side by side for gate exam too so anyone can help me in this question ?
answered Jul 26 in Theory of Computation asqwer 633 points 19 views
0 votes
1 answer 14 views
0 votes
1 answer 15 views
@Praveen Saini @Lakshman Patel RJIT @Digvijay Pandey Just wanted to ask doubt, If the minimum pumping length of the language can be 0 for any language? I think it should not be as any string will either be accepted or rejected.
answered Jul 14 in Theory of Computation asqwer 633 points 15 views
0 votes
1 answer 16 views
If a language satisfies monotonic property then is it REL or REC or NOT REL ?? And What about CO- REL?? #RICE THEOREM
answered Jul 13 in Theory of Computation asqwer 633 points 16 views
0 votes
1 answer 29 views
What are the differences between a dead state and a trap state?
answered Jul 10 in Theory of Computation asqwer 633 points 29 views
0 votes
1 answer 14 views
Construct Turing machines that will accept the following languages on {a, b}. L= {w|w| is even}.
answered Jul 10 in Theory of Computation asqwer 633 points 14 views
0 votes
1 answer 40 views
Can anyone make Dpda for the following languages L1={ a^nb^m| n>m;n,m>0} L2= { x ∈ { a, b }* | na (x) > nb (x) } I have find too little solution and but everyone violating Dpda definition like for any q€Q ,x€ T( stack symbol ) if, ∆(q, epsilon,x) !=phi then ∆(q,a,x)= phi for every a€sigma Please anyone help...
answered Jul 6 in Theory of Computation asqwer 633 points 40 views
0 votes
0 answers 7 views
Hello everyone, I am bit confused with the terms decidable, undecidable, recognizable and unrecognizable. For example for L1 I thought its decidable because the Turing machine can find word which can have a lenght of 2020. But its not the case its undecidable. I tried to ... problem so I reduce the L1 to ATM if the language is in L1 then accepts otherwise it loops forever. Thanks for your answer!
asked Jun 26 in Theory of Computation sayuri 5 points 7 views
0 votes
0 answers 9 views
hi, this is MadeEasy TOC question. It mentions to eliminate X first and then Y. How can this be done, I mean how can we eliminate X and Y since even after subsitution they will be repeating. I know here we have to use arden’s theorem but unable to understand how to reduce. Please help…....….
asked Jun 25 in Theory of Computation rish1602 9 points 9 views
1 vote
1 answer 714 views
Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free? $L_1 \cap L_2$ $L_1 \cdot L_2$ $L_1- L_2$ $L_1\cup L_2$
answered Jun 24 in Theory of Computation amitkhurana512 173 points 714 views
3 votes
1 answer 831 views
Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive? $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is ... $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$
answered Jun 18 in Theory of Computation amitkhurana512 173 points 831 views
0 votes
0 answers 14 views
Given language L = strings starting with 'a'. Sigma(Alphabet) = {a,b} DFA: It should only accept the given language and reject other languages. Therefore only strings starting with 'a' MUST be accepted by the DFA, and the strings starting with 'b' MUST ... and Regular expressions are not correctly defined by me, can you please define all these clearly so that it becomes easy to distinguish them.
asked Jun 12 in Theory of Computation akshansh 15 points 14 views
0 votes
0 answers 12 views
How is the regular expression (0+1)*0(0+1)*1(0+1)* is equivalent to (0+1)*01(0+1)* ?
asked Jun 9 in Theory of Computation hrtoimukra 5 points 12 views
0 votes
0 answers 20 views
can we make DFA for a language where there is comparion between symbols but lanuage is finite a^nb^n;n<=3
asked Jun 8 in Theory of Computation promise 5 points 20 views
0 votes
0 answers 19 views
if language is finite then dfa possible irrespective of comparison between symbols exist or not.is it true??
asked Jun 8 in Theory of Computation promise 5 points 19 views
0 votes
0 answers 9 views
It is clear than alt(L,M) is L = {(ab)+}. So dfa is possible but How to prove it formally?
asked May 29 in Theory of Computation Palash Nandi 1 13 points 9 views
0 votes
0 answers 7 views
Exercise 4.2.1.(f) Suppose h is the homomorphism from the alphabet { 0, 1, 2 } to the alphabet { a, b } defined by h(0) = a, h(1) = ab, h(ba) = ba. If L = { a(ba)* } then What is the language created by inverse_h(L) ?
asked May 29 in Theory of Computation Palash Nandi 1 13 points 7 views
1 vote
1 answer 12 views
Please Correct me if Logic is wrong. Let w = w1.w2.w3...wk, By definition of min(L), w ∈ L but any w1.w2.w3...w(k-1) doesn’t. Then NO prefix reach any final state regardless of their length. Using only prefixes of w drawing a dfa is not possible but w itself belongs to L and min(L). So dfa of min(L) exists.=> Closed.
answered May 29 in Theory of Computation Deepakk Poonia (Dee) 1.7k points 12 views
0 votes
0 answers 8 views
Check if max(L) is closed or not for max(L) : { w| w is in L but no x other than EmptyString, wx is in L }. Correct if Logic is wrong., If wx is not in L ( except x is empty ) i.e. x forces the flow to stop at a non-Final state. So unless x is Empty, constructing a ... wx lands on a final state, so is w alone. A dfa is possible for all w' in L => dfa is possible for w' for max(L) => Closed.
asked May 29 in Theory of Computation Palash Nandi 1 13 points 8 views
0 votes
0 answers 7 views
check if init(L) is closed or not where init(L) = { w | for some x, wx is in L } => Correct if Logic is wrong. Let there are n differnt state in dfa of L. Case_1: if len( wx ) >= n and wx is in L then x is either EmptyString or a loop. So deleting ... then either x is EmptyString else whether single w' reach the final state is undecidable. So., x is Empty for sure, for all w in init(L) => Closed.
asked May 29 in Theory of Computation Palash Nandi 1 13 points 7 views
0 votes
0 answers 8 views
Exercise 4.2.1.(f) Suppose h is the homomorphism from the alphabet { 0, 1, 2 } to the alphabet { a, b } defined by h(0) = a, h(1) = ab, h(ba) = ba. If L = { a(ba)* } then What is the language created by inverse_h(L) ?
asked May 27 in Theory of Computation Palash Nandi 1 13 points 8 views
1 vote
1 answer 14 views
In place of highlighted transition can we use the below transitions: epsilon,a|a , epsilon,b|b , epsilon,z0|z0 ?
answered May 24 in Theory of Computation Deepakk Poonia (Dee) 1.7k points 14 views
0 votes
1 answer 15 views
For any given NFA with ip_set = {a,b} if any transaction is Missing then can we assume a Self Loop ? For example, [T1] a b [T2] a b S S,P Q S S,P Q is P _ Q same as P P Q Q* _ _ Q* Q Q Notice in T1 for transaction(P,a) = undefined. So can we assume transaction(P,a) = P ?
answered May 19 in Theory of Computation Kanwae Kan 5 points 15 views
0 votes
1 answer 18 views
while making compound automata do we have to include the dead states too in the cartesian product ? or can we ignore the dead states and then make the compound automata?
answered May 18 in Theory of Computation aryavart 73 points 18 views
0 votes
0 answers 22 views
if $r= a+epsilon$, then the $r^+$ and $r^*$ will be same right? in a question i was solving it is asked, $r^*=r^+$ if and only if $r=epsilon$. Is this true or false as i have written an example above where $r^*$ and $r^+$ will be same.
asked May 16 in Theory of Computation rythmrana 5 points 22 views
1 vote
0 answers 27 views
The language is : number of zeroes=number of ones(which can be done by a deterministic Push down automata) say w=11101000 now we divide it to 5 parts u,v,w,x,y , where u=1 v=110 w=1 x=00 y=0 L=u.(v*i).w.(x*i).y such that i>=0 but when we put i=0 the ... . This shows that the language is not in L . But as the language can be done by a PDA , it should not have failed ,or do i not understand it ?
asked May 12 in Theory of Computation hari0943 9 points 27 views
0 votes
0 answers 15 views
1 vote
0 answers 16 views
1 vote
0 answers 12 views
Construct a left-linear grammar for the language S→ abA A → baB B → aA | bb.
asked May 3 in Theory of Computation Setsu 13 points 12 views
0 votes
0 answers 21 views
For any language L, and for any k ≥ 0, let L k denote the language obtained by concatenating any k strings from L (note that L^0 = epsilon). Suppose L1 is a context-free language and R is a regular language over the same alphabet Σ of size at least 3. The smallest value of k for which (R \ L1) k ∪ (L1 \ R) is not necessarily context-free is
asked May 2 in Theory of Computation Rashimdixit 9 points 21 views
0 votes
0 answers 14 views
Levi Ackerman: Is L= {xwywr∣x, w,y∈(a+b) +} regular? wr is reverse of w
asked May 2 in Theory of Computation Gogo6996 5 points 14 views
0 votes
0 answers 12 views
Show that the following grammar is ambiguous. S → aB|ab, A → aAB|a, B → ABb|b.
asked May 2 in Theory of Computation Sravanth0989 5 points 12 views
0 votes
0 answers 10 views
Show that the following grammar is ambiguous. S → aB|ab, A → aAB|a, B → ABb|b.
asked May 2 in Theory of Computation Sravanth0989 5 points 10 views
0 votes
0 answers 11 views
For E={a,b} construct a dfa for language L where L={w | w has a b in its 2nd last position if such a position exists}????
asked May 2 in Theory of Computation harshit_1010 5 points 11 views
0 votes
0 answers 39 views
can somebody explain how to solve this type of questions
asked Apr 26 in Theory of Computation jainanmol123 13 points 39 views
0 votes
1 answer 36 views
Construct a DFA for input alphabet {a,b} with EXACTLY 2 a’s & MORE THAN 2 b’s. (Note: Order is NOT specified in the question.)
answered Apr 21 in Theory of Computation Konan-kun 71 points 36 views
0 votes
0 answers 27 views
What is the NFA that does not accept strings ending “101” ?
asked Apr 7 in Theory of Computation shri385 5 points 27 views
To see more, click for all the questions in this category.
...