Recent questions and answers in Theory of Computation

0 votes

1 answer

1

draw dfa on w such that number of a in w mod 3 less than number of b in w mod 3

answered 34 minutes ago in Theory of Computation by Mizuki (39 points) | 15 views

0 votes

1 answer

2

Regular Expression Identities
${(a+aa+b)}^{+}={(a+b)}^{+}$

answered 41 minutes ago in Theory of Computation by Swapnil Naik (101 points) | 18 views

0 votes

1 answer

3

Identity of TOC
$(a+b)^* =a^*(ba^*)^*$ As this identity already proved. But $a^*(ba^*)^*$ couldn't generate "bab" . But $(a+b)^*$ could generate all strings over {a,b}. Then the above identity seen to be proved false. Please discuss how this is possible.

answered 3 hours ago in Theory of Computation by Vikas Verma Junior (953 points) | 14 views

+1 vote

1 answer

4

Convert FA to RE
What is the RE for the above FA?

answered 11 hours ago in Theory of Computation by Prince Sindhiya Active (2.2k points) | 32 views

0 votes

3 answers

5

doubt toc
wxw ;w,x belongs to {a,b}* this regular or dcfl or cfl??? somewhere it is written as regular but dontknow why??

answered 13 hours ago in Theory of Computation by BASANT KUMAR Junior (919 points) | 28 views

0 votes

1 answer

6

DOUBT TOC
LET L1={anbmcn |m,n>=0} L2={ancn}|n>=0} both are cfl ,what is L2-L1?? i am getting { }............please verify??

answered 13 hours ago in Theory of Computation by BASANT KUMAR Junior (919 points) | 14 views

0 votes

0 answers

7

self doubt inherently ambiguity
https://gateoverflow.in/7428/grammar-generates-inherently-ambiguous-context-language how can we check that for ambiguous grammar no unambiguous grammar exist??

asked 16 hours ago in Theory of Computation by eyeamgj Active (3.6k points) | 8 views

0 votes

0 answers

8

An Introduction to formal languages and automata

asked 18 hours ago in Theory of Computation by pratyusha619129161 (7 points) | 20 views

0 votes

1 answer

9

toc complement
L={wxwR |w belongs to(a+b)* ,x belong to (a+b)} the complement of language L is ???? A)regular B)dcfl but not regular C)cfl but not dcfl D)none of these answer given is c but any example is there please provide??

answered 19 hours ago in Theory of Computation by Vikas Verma Junior (953 points) | 16 views

0 votes

1 answer

10

Test Series
a. Regular, b. DCFL, c. CFL but not DCFL

answered 23 hours ago in Theory of Computation by daksirp (401 points) | 28 views

0 votes

0 answers

11

self doubt toc
assume pda stack is limited to 210 symbols .now stack can contain maximum of 2^10 symbols The language Accepted by such pda is a)regular lang but not finite b)dcfl but not regular c)cfl but not dcfl d)non of these actually my doubt is that pda with finite stack is equivalent to finite automata so it will accept regular language is fine but not finite how???

asked 1 day ago in Theory of Computation by eyeamgj Active (3.6k points) | 7 views

0 votes

1 answer

12

self doubt decidability
A Turing machine can compute product of any two numbers, hence decidable problem Turing machine can perform product of two numbers, then it is an undecidable problem what is the meaning of computing and performing here???

answered 1 day ago in Theory of Computation by Shiv Gaur (275 points) | 12 views

0 votes

1 answer

13

Pda regular
pplease expain this statement

answered 1 day ago in Theory of Computation by BASANT KUMAR Junior (919 points) | 13 views

0 votes

2 answers

14

TOC, RL
Consider the following language L = {w ∈ (a+b)* | w has atleast as many occurrences of (bba)’s as (abb)’s}. Which of the following statements is/are true? S1: Language L is regular. S2: Complement of L is CFL. S3: Complement of L is CSL. S4: Reversal of L is CFL.

answered 1 day ago in Theory of Computation by shubham02 (35 points) | 18 views

+1 vote

1 answer

15

Peter Linz Exercise 5.1
Find context free grammars for the following languages (with n>=0, m>=0, k>=0) (a) L={anbmck : n=m or m<=k} (b) L={ anbmck : n=m or m≠k} (c) L={anbmck : k=n+m } (d) L={ anbmck : n+2m=k} (e) L={anbmck : k=|n-m| } (f) L={ w ∈ {a,b,c}* : na(w)+nb(w)≠nc(w) } (g) L={ anbmck : k≠n+m } (h) L= { anbmck : K>=3}

answered 1 day ago in Theory of Computation by shubham02 (35 points) | 388 views

0 votes

1 answer

16

Self Doubt in checking whether a language is regular or not

answered 1 day ago in Theory of Computation by Vikas Verma Junior (953 points) | 36 views

0 votes

1 answer

17

closure properties of cfl
cfl are closed under a) min b)max c)half d)alt e)none of these cfl are not closed under init l/a cycle set diffeence

answered 1 day ago in Theory of Computation by Shubhgupta Active (2.2k points) | 24 views

0 votes

1 answer

18

Toc book
A good book of TOC for GATE ??

answered 1 day ago in Theory of Computation by Sumit Singh Chauhan Junior (939 points) | 26 views

0 votes

1 answer

19

SELF DOUBT DCFL
SUPPOSE WE HAVE A SITUATION IN BETWEEN LIKE THIS (DCFL) INTERSECTION (REGULAR LANG)..............................SITUATION 1 NOW WE CAN WRITE DCFL IN PLACE OF REGULAR SO IT WILL BECOME DCFL INTERSECTION DCFL AND WE KNOW DCFL IS NOT CLOSED UNDER ... THAT SITUATION 1 CAN BE READ AS DCFL IS CLOSED UNDER REGULAR INTERSECTION HENCE DCFL ...........WHY THIS CONTRADICTION IS ARISING??????

answered 1 day ago in Theory of Computation by Hradesh patel Loyal (7.1k points) | 20 views

0 votes

1 answer

20

Regular languages
Kindly give the reason behind 2 and 3?

answered 2 days ago in Theory of Computation by Hradesh patel Loyal (7.1k points) | 35 views

0 votes

4 answers

21

Context Free Language
L= { $a^{n}b^{m}$ | $n<=m<=2n$ } a) DCFL b) CFL but not DCFL c) Not CFL

answered 2 days ago in Theory of Computation by Vikas Verma Junior (953 points) | 135 views

0 votes

1 answer

22

SELF DOUBT REDUCTION
IF P1 IS REDUCIBLE TO P2 AND P1 IS RECURSIVE ENUMERABLE THEN P2 NEED NOT BE RECURSIVE ENUMERABLE ???IS IS TRUE ??WHAT I AM THINKING IS THAT P1 IS UNDECIABLE SO P2 WILL ALSO BE UNDECIABLE HENCE SHOULD BE RECURSIVE ENUMERABLE...

answered 2 days ago in Theory of Computation by Spider1896 (131 points) | 72 views

0 votes

1 answer

23

true or false finite automata
finite automata have no storage and no computing capability????

answered 2 days ago in Theory of Computation by smsubham Loyal (6.8k points) | 26 views

+1 vote

1 answer

24

Context Free language
0^i1^j0^k|j=max(i,k) is CFL or not pls explain?

answered 2 days ago in Theory of Computation by Vikas Verma Junior (953 points) | 24 views

0 votes

0 answers

25

DECIDABILITY
WHICH OF THE FOLLOWING IS DECIDABLE? 1.WHEATHER AN ARBITRARY TURING MACHINE PRINTS SOME NON BLANK CHARACTER 2.WHEATHER A TURING MACHINE PRINTS A SPECIFIC CHARACTER 3.THE SET OF CODES FOR TURING MACHINE THAT NEVER MAKE A LEFT MOVE. 4. WHEATHER T.M EVER MOVES ITS HEAD TO ... STATE Q WHEN STARTED WITH INPUT W FROM ITS INITIAL STATE 6.T.M VISITS STATE Q ON SOME INPUT WITHIN 10 STEPS. 7.

asked 3 days ago in Theory of Computation by eyeamgj Active (3.6k points) | 16 views

0 votes

1 answer

26

self doubt
find the number of trivial substring in "SAME1234".

answered 3 days ago in Theory of Computation by Deepanshu Junior (707 points) | 24 views

+1 vote

1 answer

27

TOC language is CFL or not
L={a^n,b^n,c^m / n>m} we have to compare n and m everywhere I know till we reach b there will be nothing in the stack BUT generally we can make this language if possible suppose when we are putting one a into the stack suppose we put Two a's ... string I'm asking this question because in one of the video for the question we were taking two a's on behalf of one .......

answered 3 days ago in Theory of Computation by Sumit Singh Chauhan Junior (939 points) | 52 views

+2 votes

2 answers

28

toc cfl or not ?
L={ ai bj ck | i,j,k>=0, i<j<k} CFL OR NOT CFL ??

answered 3 days ago in Theory of Computation by Sumit Singh Chauhan Junior (939 points) | 129 views

0 votes

0 answers

29

Toc prefixes
What is init operation?

asked 3 days ago in Theory of Computation by shipra tressa (253 points) | 15 views

0 votes

0 answers

30

TOC, REL
Set of all languages that are not Recursively Enumerable is uncountable. This is true. WHY? [closed]

asked 3 days ago in Theory of Computation by manisha11 (197 points) | 6 views

0 votes

2 answers

31

nfa to dfa
Consider the following NFA for ∑={ g,a,t,e}.Find the number of states in equivalent minimal dfa. a)4 b)5 c)6 d)8

answered 3 days ago in Theory of Computation by Swapnil Naik (101 points) | 41 views

0 votes

1 answer

32

self doubt
halting problem for turing machine is undecidable it is clear but what about halting problem of total turing mchine???

answered 3 days ago in Theory of Computation by Deepanshu Junior (707 points) | 13 views

0 votes

0 answers

33

please answer and verify it
https://gateoverflow.in/168678/madeeasy-work-book

asked 3 days ago in Theory of Computation by eyeamgj Active (3.6k points) | 25 views

+1 vote

1 answer

34

Regular expression
Writw the regular expression with explaination

answered 3 days ago in Theory of Computation by arvin Active (3.5k points) | 36 views

+2 votes

2 answers

35

TOC Countability
Let A and B be countably infinite set which of the following is false :- a.) any subset of a or b is countable infinite b:) A union B and A*B is countable infinite c:)the union of countable infinite collection of countably infinite sets is countable infinite d)cartesian product of countable infinite collection of countable infinite sets is countable infinite

answered 3 days ago in Theory of Computation by arvin Active (3.5k points) | 363 views

0 votes

1 answer

36

Thoery of computation
Eplison + R =

answered 4 days ago in Theory of Computation by sumedha bhatia (211 points) | 23 views

0 votes

0 answers

37

TOC SELF DOUBT
https://gateoverflow.in/141979/toc-countability HOW TO PROVE B,C,D TRUE??

asked 4 days ago in Theory of Computation by eyeamgj Active (3.6k points) | 20 views

0 votes

2 answers

38

RE Ques
Describe in simple English the language represented by the regular expression r=(1+10)*

answered 4 days ago in Theory of Computation by manisha11 (197 points) | 43 views

0 votes

0 answers

39

Construction of DFA
Why is the construction of DFA possible for an equal number of 110's and 011's, but not possible for an equal number of 0's and equal number of 1's?

asked 4 days ago in Theory of Computation by Ajit J (57 points) | 27 views

+2 votes

3 answers

40

dfa problem
Construct a minimal DFA, which accepts set of all strings over {0, 1}, which when interpreted as binary number is divisible by ‘3’. , IS IS this solution right because null string is also accepted which is not in language

answered 4 days ago in Theory of Computation by Ajit Singh Rajawat (11 points) | 316 views

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

Recent questions and answers in Theory of Computation

Recent Posts

Recent Blog Comments