Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Exams
Recent questions tagged theoryofcomputation
0
votes
0
answers
NIELIT Scientist B 2016
Which of the following is wrong: A. Turing machine is a simple mathematical model of general purpose computer B. Turing machine is more powerful than finite automata C. Turing machine can be simulated by a general purpose computer D. All of the above ... are wrong. Turing machine is more powerful than finite automata is true, similarly option C and A also seems to be true.
asked
3 minutes
ago
in
Theory of Computation
by
Ollie
(
6
points)

1
view
theoryofcomputation
turingmachine
0
votes
0
answers
what is the Meaning of following in peter linz algortihm for Chapter 3 , Nfa to Rex?
asked
1 day
ago
in
Theory of Computation
by
lokopi
(
6
points)

8
views
theoryofcomputation
peterlinz
0
votes
0
answers
Self Doubt 5:Peter Linz(exercise 1.2)
$L1={a^{n} b^{m};n>=0,m<n}$ $L2={a^{n} b^{(n2)};n>=3}$ $L3=complement$ $of$ $L2.$ $L1L3$ is? According to me $L1L3$ is same as $L2$. Please verify.
asked
1 day
ago
in
Theory of Computation
by
Doraemon
(
100
points)

14
views
theoryofcomputation
peterlinz
0
votes
1
answer
self doubt 4 Peter Linzchapter 7.
It has been told in Peter Linz that if L1 is deterministic contextfree and L2 is regular, then a) the language L1 ∪ L2 is deterministic contextfree b) the language L1 ∩ L2 is deterministic contextfree. But DCFL is not closed under ... regular language is a DCFL then automatically , therefore L1UL2 and L1 ∩ L2 might not be closed. Can anyone please verify?
asked
2 days
ago
in
Theory of Computation
by
Doraemon
(
100
points)

12
views
theoryofcomputation
peterlinz
0
votes
1
answer
self doubt 2PDA
If suppose we have an NPDA for a language,Does that mean that the language is always NCFL?
asked
3 days
ago
in
Theory of Computation
by
Doraemon
(
100
points)

11
views
theoryofcomputation
0
votes
0
answers
SELF DOUBT3(PDA)
Can someone give me the PDA for this language? L={W BELONGS TO {a+b+c}*; (no. of a+no. of b) not equal to the number of c} Actuallly I am getting a NPDA for this .does this language have a DPDA?
asked
3 days
ago
in
Theory of Computation
by
Doraemon
(
100
points)

5
views
theoryofcomputation
0
votes
0
answers
REQUEST FOR SOLTION MANUAL FOR PETER LINZ
Can anyone provide me with the solution manual for 6TH EDITION OF PETERLINZ.(or if not available any edition you have)
asked
3 days
ago
in
Theory of Computation
by
Doraemon
(
100
points)

4
views
theoryofcomputation
peterlinz
0
votes
1
answer
TYPE OF THE LANGUAGEPeter Linz chapter 4
L={a^n:n is either prime or product of 2 or more prime numbers} According to me this is regular. Can anyone verify?
asked
5 days
ago
in
Theory of Computation
by
Doraemon
(
100
points)

20
views
theoryofcomputation
peterlinz
0
votes
1
answer
self doubt on toc finit automata
What will be the number of states in minimal DFA, if every string contains aa and bb as substring ?
asked
Mar 20
in
Theory of Computation
by
Sankalp Singh 1
(
6
points)

20
views
#dfa
finiteautomata
theoryofcomputation
0
votes
1
answer
Context free language doubt 1
Ravi considers two CFLs L1 and L2, performs the following operation on both the languages. (i) He unions L1 and L2 to obtain a new language L3 (ii) He concatenates L1 and L3 to obtain L4 (iii) He takes complement of L4 to obtain L5 The language L5 is a.REL but not Recursive b.Recursive but not CSL c.CFL but not CSL d.CSL
asked
Mar 10
in
Theory of Computation
by
Shivateja MST
(
113
points)

20
views
theoryofcomputation
0
votes
1
answer
Regular Languages self doubt
What is the language given by this : ${\color{Red} {a^mb^nLCM(m,n)<=1}}$
asked
Mar 9
in
Theory of Computation
by
Abhipsa
(
17
points)

13
views
theoryofcomputation
#toc
#regularlanguage
0
votes
1
answer
Automata  DFA
In what cases we need to include epsilon in DFA.
asked
Feb 18
in
Theory of Computation
by
pppankajsaini
(
8
points)

23
views
#dfa
theoryofcomputation
#toc
0
votes
0
answers
regular expression self doubt
Given the regular expression L(ab*aa+bba*ab). in this question my doubt is what is the number of states in minimum nfa and minimum dfa for this expression.
asked
Feb 17
in
Theory of Computation
by
aerox
(
7
points)

9
views
theoryofcomputation
peterlinz
0
votes
0
answers
peterlinz theory of computation
mu doubt is what will be the number of states in minimum nfa and minimum dfa for this regular expression of question 1 given by L(ab*aa+bba*ab)
asked
Feb 17
in
Theory of Computation
by
aerox
(
7
points)

4
views
theoryofcomputation
+1
vote
0
answers
Turing Machine
As per the definition of a Turing Machine, it does not accept Epsilon. But, A → ϵ can be generated by a Unrestricted Grammar. So, how can we say that Turing Machines are the acceptors for Recursively Enumerable languages generated by Unrestricted Grammar?
asked
Feb 13
in
Theory of Computation
by
Joon88
(
7
points)

18
views
#toc
turingmachine
theoryofcomputation
grammar
unrestrictedgrammar
+1
vote
0
answers
TOC(self doubt)
How is the complement of $L=\{ww w \epsilon(a+b)^*\}$ is $CFL$
asked
Feb 5
in
Theory of Computation
by
Pratyush Priyam Kuan
(
804
points)

22
views
theoryofcomputation
#closureproperties
#toc
0
votes
0
answers
Made Easy:Mock
$L$:{$a^{n} b^{n+k} / n>=0,k>=1$} $\cup$ {$a^{n+k} b^{n} /n>=0,k>=3 $} Is it a DCFL?
asked
Feb 3
in
Theory of Computation
by
Sambhrant Maurya
(
401
points)

49
views
theoryofcomputation
0
votes
1
answer
Pumping Lemma (self doubt)
I am not able to understand how $r=0^*1 + 0 + 1^* + 10^*1$ has minimum pumping length of 2 as given in https://gateoverflow.in/303738/michaelsipserexercise . Can someone please explain? Thank you
asked
Feb 2
in
CO & Architecture
by
Pratyush Priyam Kuan
(
804
points)

32
views
theoryofcomputation
pumpinglength
0
votes
0
answers
SELF DOUBT: REGULAR LANGUAGE AND CFL
Let $A$ be a $regular$ $language$ and $B$ be a $CFL$ over the alphabet $\sum$. Which of the following statement about the given language $R$, where $R=\bar{A}B$ is $True?$ $R$ is $necessarily$ $CFL$ but $not$ $necessarily$ $regular$ R is $necessarily$ $regular$ but $infinite$ R is $necessarily$ $non$ $regular$ $None$
asked
Feb 1
in
Theory of Computation
by
Debapaul
(
699
points)

32
views
theoryofcomputation
0
votes
0
answers
Ambiguity in Grammar
Which CFG has equivalent unambiguous CFG ? Please help me to understand between inherently ambiguous and simple ambiguous grammar. I know how to check for ambiguity in grammar,just check if there are more than 2 derivation tree possible for a given string. But I don’t know how to check if a grammar is inherently ambiguous grammar
asked
Feb 1
in
Theory of Computation
by
s_dr_13
(
16
points)

12
views
compilerdesign
theoryofcomputation
0
votes
0
answers
made easy mock 3
l is regular only if h(l) is regular. h(l) is regular only if l is regular. Which of the statement is true? I can’t understand why second statement is false if regular languages are closed under inverse homomorphism then second statement should be true
asked
Feb 1
in
Theory of Computation
by
abhinav649
(
67
points)

15
views
#gatepreparation
theoryofcomputation
0
votes
0
answers
undecidability pdf given on gatecse rice's theorem
asked
Jan 31
in
Theory of Computation
by
shethnisarg
(
6
points)

10
views
recursiveenumurablelanguage
#ricestheorem
theoryofcomputation
turingmachine
0
votes
0
answers
TOC : Ace test series (Semi decidable)
asked
Jan 30
in
Theory of Computation
by
Chirag Shilwant
(
180
points)

22
views
aceacademytestseries
theoryofcomputation
recursiveenumurablelanguage
decidability
0
votes
0
answers
Madeeasy test series  Number of strings present
asked
Jan 26
in
Theory of Computation
by
luc_Bloodstone
(
36
points)

26
views
madeeasytestseries
theoryofcomputation
prefixproperty
0
votes
0
answers
SELF DOUBT: PREVIOUS GO NUMBER OF STATES IN DFA
The number of possible Deterministic Finite Automation with two states $q0$ and $q1$, where $q0$ is always the initial state over the alphabet $\{a,b\}$ which accept empty language is : ____________. I have solved it like this, for $q0$ on $i/p$ $a$ ... or nonfinal so we have $2$ choices for it, hence total $2^2 * 2^2 * 2=32$ Is my approach right?
asked
Jan 25
in
Theory of Computation
by
Debapaul
(
699
points)

18
views
theoryofcomputation
0
votes
0
answers
TOC GeeksForGeeks
Consider the following nondeterministic finite automaton (NFA) over the alphabet Σ = {0, 1}. Language of the above NFA is
asked
Jan 24
in
Theory of Computation
by
ShrutiS
(
6
points)

20
views
theoryofcomputation
#regularlanguage
0
votes
0
answers
GATE 2015 Question
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3SAT 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 NPhard (B) Q2 is in NP, Q1 is NPhard (C) Both Q1 and Q2 are in NP (D) Both Q1 and Q2 are NPhard
asked
Jan 20
in
Theory of Computation
by
veenashiva18
(
7
points)

5
views
theoryofcomputation
decidability
0
votes
1
answer
TOC : ACE TEST SERIES
asked
Jan 19
in
Theory of Computation
by
Chirag Shilwant
(
180
points)

15
views
aceacademytestseries
theoryofcomputation
0
votes
0
answers
TOC Ace test series
asked
Jan 19
in
Theory of Computation
by
Chirag Shilwant
(
180
points)

6
views
aceacademytestseries
theoryofcomputation
contextfreelanguages
0
votes
0
answers
Self Doubt : TOC
Q. REL(which is REC) $\cup$ REL(which is not REC) =?
asked
Jan 19
in
Theory of Computation
by
Chirag Shilwant
(
180
points)

7
views
theoryofcomputation
#closureproperties
0
votes
0
answers
applied gate:TOC
asked
Jan 17
in
Theory of Computation
by
abhinav649
(
67
points)

48
views
theoryofcomputation
0
votes
1
answer
ace test series toc cfl rel
Q.
asked
Jan 11
in
Theory of Computation
by
Rahul Burman
(
21
points)

19
views
theoryofcomputation
aceacademytestseries
contextfreelanguages
recursiveenumurablelanguage
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.
asked
Jan 8
in
Theory of Computation
by
abhinav649
(
67
points)

14
views
testbooktestseries
theoryofcomputation
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.
asked
Jan 7
in
Theory of Computation
by
goxul
(
377
points)

44
views
theoryofcomputation
contextfreelanguages
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
asked
Jan 7
in
Theory of Computation
by
tamaldeepmaity
(
17
points)

37
views
madeeasytestseries
theoryofcomputation
contextfreelanguages
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 nonempty will be in $L$. So L is a set of all nonempty CFL's. How to proceed?
asked
Jan 4
in
Theory of Computation
by
Mk Utkarsh
(
505
points)

44
views
theoryofcomputation
decidability
madeeasytestseries
0
votes
0
answers
ACe mock test 4 Q54
Please explain the meaning of the question
asked
Jan 4
in
Theory of Computation
by
ssap09
(
42
points)

7
views
#gatepreparation
aceacademytestseries
theoryofcomputation
#decidability
0
votes
1
answer
demo test madeeasy Q13
Which of the following statement is true? In answer : S2 is correct. But how? please tell the approach to solve this type of question
asked
Dec 30, 2019
in
Theory of Computation
by
ssap09
(
42
points)

58
views
madeeasytestseries
theoryofcomputation
#gatepreparation
0
votes
0
answers
MADE EASY fyll length test series
If the given language $L:\{(aa)^n (bb)^m (aa)^nm,n>=0\}$ & homomorphic function $h(0)=aa$ $h(1)=bb$ $h(2)=aa$ Then $h^{1}(L)$ will be $\{0^n 1^m 2^nm,n>=0\}$ $\{2^n 1^m 0^n m,n>=0\}$ $\{0^n 1^n 0^nm,n>=0\}$ none of the above Ans is D
asked
Dec 30, 2019
in
Theory of Computation
by
SHARMISTHA CHOUDHURY
(
7
points)

33
views
theoryofcomputation
contextfreelanguages
0
votes
1
answer
MadeEasy FULL SYLLABUS TEST1 (BASIC LEVEL) GATE 2020 Q51
asked
Dec 29, 2019
in
Theory of Computation
by
DukeThunders
(
415
points)

63
views
theoryofcomputation
contextfreelanguages
Page:
1
2
3
4
5
next »
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
Apr 2020
!KARAN
36 Points
lazygatestudent
5 Points
AngeloAlba89
5 Points
WillKnisley
5 Points
TamieMcvay4
5 Points
Satyaki Das
5 Points
akansha03
5 Points
Doraemon
3 Points
srestha
3 Points
Shivateja MST
2 Points
Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
3,513
questions
1,656
answers
10,451
comments
90,037
users