Recent questions tagged toc-languages
Register

Recent questions tagged toc-languages

Recent questions tagged toc-languages
0 votes
0 answers 39 views
Gate applied
Can some one please do a pumping lema on L = {a^(2n+1) | n>=0 } I know Finite automata can be easily made and hence it is a regular language, but the pumping lema test fails for this implying it is a non-regular language (I am sure I am doing the pumping lema wrong) can someone please do a pumping lema for this so that I compare my solution and rectify my mistake
pavan.varyani asked in Theory of Computation Dec 7, 2021
by pavan.varyani
5 points
39 views
0 votes
0 answers 195 views
Countability in toc
Hi What is best resource and Where to study countability topic in toc?
ykrishnay asked in Theory of Computation Aug 21, 2021
by ykrishnay
103 points
195 views
0 votes
0 answers 39 views
How to design Turing machine for addition of 2 binary numbers
ykrishnay asked in Theory of Computation Aug 18, 2021
by ykrishnay
103 points
39 views
1 vote
0 answers 53 views
complement of language
How to find complement of language.? complement of recursive language is recursive. while complement of context free language is context sensitive language.
TheShivam asked in Theory of Computation Aug 16, 2021
by TheShivam
9 points
53 views
0 votes
0 answers 45 views
Regular Grammar
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?
Shubhranshu asked in Theory of Computation Aug 1, 2021
by Shubhranshu
5 points
45 views
0 votes
0 answers 35 views
Clear distinction between Finite automata, Regular expressions
akshansh asked in Theory of Computation Jun 12, 2021
by akshansh
15 points
35 views
0 votes
0 answers 59 views
NPTEL(Theory of Computation )
How is the regular expression (0+1)*0(0+1)*1(0+1)* is equivalent to (0+1)*01(0+1)* ?
hrtoimukra asked in Theory of Computation Jun 9, 2021
by hrtoimukra
5 points
59 views
0 votes
0 answers 28 views
$r^+$ and $r^*$doubt from TOC[self doubt]
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.
rythmrana asked in Theory of Computation May 16, 2021
by rythmrana
5 points
28 views
1 vote
0 answers 42 views
Peter Linz 6th Edition Chapter 3 Exercise 3.3 Q 4
Construct a left-linear grammar for the language S→ abA A → baB B → aA | bb.
Setsu asked in Theory of Computation May 3, 2021
by Setsu
13 points
42 views
1 vote
0 answers 23 views
Peter Linz 6th Edition Chapter 3 Exercise 3.3 Q 4
Construct a left-linear grammar for the language S→ abA A → baB B → aA | bb.
Setsu asked in Theory of Computation May 3, 2021
by Setsu
13 points
23 views
0 votes
0 answers 42 views
Ullman,rozen
Levi Ackerman: Is L= {xwywr∣x, w,y∈(a+b) +} regular? wr is reverse of w
Gogo6996 asked in Theory of Computation May 2, 2021
by Gogo6996
5 points
42 views
0 votes
0 answers 36 views
DFA construction
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}????
harshit_1010 asked in Theory of Computation May 2, 2021
by harshit_1010
5 points
36 views
0 votes
0 answers 21 views
#DFA Introduction, Formal Languages, DFA Construction examples
DarkShadow18 asked in Theory of Computation Apr 10, 2021
by DarkShadow18
5 points
21 views
0 votes
0 answers 43 views
AppliedGate lecture example
What is the NFA that does not accept strings ending “101” ?
shri385 asked in Theory of Computation Apr 7, 2021
by shri385
5 points
43 views
0 votes
0 answers 47 views
PDA for a^nb^n/n>=1
Is this PDA correct for a^n. B^n/n>=1?
jaswanth431 asked in Theory of Computation Mar 4, 2021
by jaswanth431
5 points
47 views
0 votes
0 answers 55 views
made easy test series
Answer given is “All of these” My answer is none of these are regular.
rahul65 asked in Theory of Computation Feb 3, 2021
by rahul65
5 points
55 views
0 votes
0 answers 159 views
TOC Made easy
Consider the grammar consisting of seven productions. S → aA | aBB A → aaA | λ B → bB | bbC C → B After elimination of unit, useless, and λ -productions how many productions remain in the resulting grammar ? 2 3 4 5
kirtipurohit asked in Theory of Computation Feb 2, 2021
by kirtipurohit
15 points
159 views
0 votes
0 answers 76 views
Gate Overflow itself
Is the explanation is correct? Link-https://gateoverflow.in/33183/complement-of-csl If I say complement of $a^{n}b^{n}c^{n} \, \, \, \, \, \, is\, \, \, \, \, a^{n}b^{n}c^{m} \: \: and\: \: \: m\neq n$ Then How Can it be regular?
RavGopal asked in Theory of Computation Feb 1, 2021
by RavGopal
145 points
76 views
0 votes
0 answers 74 views
self doubt - decidability
L={<M>| M is a TM that accepts all even numbers}. How to check whether it is RE, REC or not RE… I think Rice’s theorem 2nd part is not applicable here
Abhineet Singh asked in Theory of Computation Feb 1, 2021
by Abhineet Singh
23 points
74 views
1 vote
0 answers 69 views
Recursive Languages Self Doubt
Is recursive language closed under positive closure?
aditi19 asked in Theory of Computation Jan 29, 2021
by aditi19
59 points
69 views
0 votes
0 answers 60 views
Madeeasy Test series TOC Q1
Shivateja MST asked in Theory of Computation Jan 23, 2021
by Shivateja MST
45 points
60 views
0 votes
0 answers 28 views
An introduction to formal languages and automata
How can I explain that this language- L= { a<sup>n</sup> b<sup>l</sup> : n ≠ l } is not regular. [USE PUMPING LEMMA OR CLOSURE PROPERTIES] This question is under a book named An introduction to ... understandable manner and show how you exactly arrived at the solution? That would be a great help to me. Thanks in advance
kirtipurohit asked in Theory of Computation Jan 18, 2021
by kirtipurohit
15 points
28 views
0 votes
0 answers 92 views
An introduction to formal languages and automata peter linz
kirtipurohit asked in Theory of Computation Jan 16, 2021
by kirtipurohit
15 points
92 views
0 votes
0 answers 24 views
Peter Linz 5e Ex-2.1 Q-7e DFA
Find DFA on $\Sigma =(a,b)$ for L={ w : $(n_{a}(w)-n_{b}(w))mod3>0$ }
aditi19 asked in Theory of Computation Jan 14, 2021
by aditi19
59 points
24 views
1 vote
0 answers 44 views
Peter Linz 5e Ex-2.1 Q7e DFA
Find DFA on $\Sigma =(a,b)$ for L={ w : $(n_{a}(w)-n_{b}(w))mod3>0$ }
aditi19 asked in Theory of Computation Jan 14, 2021
by aditi19
59 points
44 views
0 votes
0 answers 43 views
GATE 2003 , Theory Of Computation , Turing Machine
Pushkar Khadase asked in Theory of Computation Jan 4, 2021
by Pushkar Khadase
5 points
43 views
0 votes
0 answers 19 views
Introduction to Languages and The Theory of Computation
aryan1234 asked in Theory of Computation Dec 23, 2020
by aryan1234
5 points
19 views
0 votes
0 answers 36 views
Introduction to Languages and The Theory of Computation John C. Martin North Dakota State University
aryan1234 asked in Theory of Computation Dec 23, 2020
by aryan1234
5 points
36 views
0 votes
0 answers 16 views
Introduction to Languages and The Theory of Computation John C. Martin
aryan1234 asked in Theory of Computation Dec 23, 2020
by aryan1234
5 points
16 views
Page:
Ask a Question
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.
Developed by Chun