Recent questions and answers in Theory of Computation

0 votes

0 answers

1

ace test series
someone please explain option (C) and option (D)....... (ANSWER IS B).

asked 2 hours ago in Theory of Computation by newdreamz a1-z0 (227 points) | 22 views

0 votes

1 answer

2

Formal Languages
If G= ({S} , {a}, {S--->SS} , S), then language L(G) is a)ϕ b)aa(a)* c)(aa)* d)None of these

answered 8 hours ago in Theory of Computation by Ollie (111 points) | 9 views

0 votes

0 answers

3

made easy
Mrs Neha worked for her project , designed two operations given below and asked her students to check whether language L is closed under below operations or not: operation1(L): {wϵ L| no proper prefix of w is a member of L} operation2(L): {wϵ L| w is ... regular, then it is closed under operation2 but not under operation1. (D) if L is regular, then it is not closed under any operation.

asked 13 hours ago in Theory of Computation by talha hashim Active (3.4k points) | 25 views

0 votes

0 answers

4

TOC Self Doubt
If L1 is CFL and L2 is Regular L. $L1\cap L2 = L3$ Then L3 is CFL. Can L3 be regular also sometimes and if L3 is CFL and Regular also does it employs L1 is also Regular ??

asked 21 hours ago in Theory of Computation by jatin khachane 1 Junior (757 points) | 19 views

0 votes

0 answers

5

Regular Languages
Which is the equivalent Regular Expression for the following: "Strings in which every group of 3 symbols should contain atleast 1 a." a)[(a+b) (a+b)a]* b) [(a+b) (a+b)a]* [(a+b)(a+b)a]* c)[(ϵ + b + bb)a]* [ ϵ+ b + bb] d) (abb)* (bab)b* (bba)*

asked 22 hours ago in Theory of Computation by Sambhrant Maurya Junior (731 points) | 14 views

0 votes

0 answers

6

Formal Languages
Let r1 = (b*ab*ab*ab*)* and r2= (b*ab*ab*)*. What is L(r1) ∩ L(r2)? a) L[b*ab*ab*ab*)*] b) L[b*ab*ab*)*] c) L[b*ab*ab*)6] d) L[b*ab*ab*ab*ab*ab*ab*)*]

asked 22 hours ago in Theory of Computation by Sambhrant Maurya Junior (731 points) | 10 views

0 votes

0 answers

7

Formal Languages
Let r1= (a+b2)* , r2 = (a* + b*)* , r3 = (a2 + b)* Which of the following is true? a)L(r1) is a subset of L(r2) and L(r3) is a subset of L(r2) b)L(r2) is a subset of L(r1) and L(r2) is a subset of L(r3) c)L(r1) = L(r3) is a subset of L(r2) d) L(r1) U L(r3) = L(r2)

asked 22 hours ago in Theory of Computation by Sambhrant Maurya Junior (731 points) | 7 views

0 votes

0 answers

8

TOC SELF DOUBT
L = { w ∈ {a,b}* : a(w) = b(w) } We're using the notation: a(w) = number of a's in a string w b(w) = number of b's in a string w S⇾ aSbS | bSaS | ε Doubt: Is the same language generated by below grammar also: S⇾ SS | aSb | bSa | ε

asked 1 day ago in Theory of Computation by jatin khachane 1 Junior (757 points) | 17 views

0 votes

0 answers

9

Concatenation of DCFLs
L1={an bn | n>=0} L2={bn cn | n>=0} What is L1.L2 ? Is it an b2n cn ?

asked 1 day ago in Theory of Computation by sripo (247 points) | 17 views

0 votes

1 answer

10

automata4
according to me this should be false,but given answer is true!

answered 1 day ago in Theory of Computation by Verma Ashish Active (1.5k points) | 9 views

0 votes

0 answers

11

Grammar to DFA Construction
For the given Grammar S->aA|bB A->bC|aS B->aC|bS C->aB|bA Construct DFA I am getting confused in understanding how to take the final state.

asked 1 day ago in Theory of Computation by sripo (247 points) | 16 views

0 votes

2 answers

12

Regular Languages
Why is WXWR a regular language but XWWR is not? (X,W ϵ (0,1)+)

answered 1 day ago in Theory of Computation by garimanand Junior (643 points) | 32 views

+1 vote

2 answers

13

self doubt
LB = { < M > | M is a valid Turing Machine } is decidable or undecidable.

answered 1 day ago in Theory of Computation by garimanand Junior (643 points) | 80 views

0 votes

1 answer

14

APDCL 2017 Which one of the following regular expressions....

answered 1 day ago in Theory of Computation by garimanand Junior (643 points) | 30 views

0 votes

2 answers

15

Self Doubt in checking whether a language is regular or not

answered 1 day ago in Theory of Computation by suvradip das (53 points) | 54 views

0 votes

0 answers

16

APDCL 2017
Consider the grammarr S -> sS More in the image below:

asked 2 days ago in Theory of Computation by Hriday Das 1 (51 points) | 17 views

+1 vote

0 answers

17

Subset of a regular language
Let L be a regular language over {a,b}, Suppose a new language defined as follows, L = x1 , x2, x3, x4,........ L1 = x5, x10, x15 ..... L1 is defined as taking every string which is at positon 5, 10, 15 and so on, in other words, the positions that can be divided by 5. Is L1 regular?

asked 2 days ago in Theory of Computation by AnilGoudar Active (4.6k points) | 12 views

0 votes

0 answers

18

automata6

asked 2 days ago in Theory of Computation by Gate Fever Junior (933 points) | 21 views

0 votes

0 answers

19

automata5

asked 2 days ago in Theory of Computation by Gate Fever Junior (933 points) | 14 views

0 votes

0 answers

20

automata7

asked 2 days ago in Theory of Computation by Gate Fever Junior (933 points) | 8 views

0 votes

0 answers

21

automata5
FROM OPTIONS ONLY IT IS VERY EASY TO GUESS THAT IT IS OPTION C,BUT I WANT TO KNOW THE REASON WHY COMPLEMENT OF UNDECIDBLE LANGUAGE IS ALL POSSIBLE LANGUAGES

asked 2 days ago in Theory of Computation by Gate Fever Junior (933 points) | 7 views

0 votes

0 answers

22

AUTOMATA
PLS EXPLAIN

asked 2 days ago in Theory of Computation by Gate Fever Junior (933 points) | 11 views

0 votes

0 answers

23

automata3

asked 2 days ago in Theory of Computation by Gate Fever Junior (933 points) | 11 views

0 votes

0 answers

24

automata2

asked 2 days ago in Theory of Computation by Gate Fever Junior (933 points) | 5 views

0 votes

0 answers

25

automata1

asked 2 days ago in Theory of Computation by Gate Fever Junior (933 points) | 12 views

0 votes

0 answers

26

pushdownauto
Consider the below mentioned PDA M1 (Q, ∑, Г, δ, q0, Z, F) which accepts thelanguage L. Where: Q={q0, q1, q2, q3, q4} Σ={a,b} Г={a,b,Z} Z=initial pushdown symbol F=set of final states, empty in this case as the string is accepted by null store. Choose the correct Grammar ... . 1. S → aaBb|aab, B → aaBb|aab 2. None of the above. 3. S →aaBb|∊, B →aaBb|aab 4. S →aaBb|aab|∊, B →aaBb|aab

asked 2 days ago in Theory of Computation by Bhupendra (229 points) | 4 views

0 votes

0 answers

27

push down automata
Consider the below mentioned PDA M1 (Q, ∑, Г, δ, q0, Z, F) which accepts thelanguage L. Where: Q={q0, q1, q2, q3, q4} Σ={a,b} Г={a,b,Z} Z=initial pushdown symbol F=set of final states, empty in this case as the string is accepted by null store. Choose the correct ... 1. S → aaBb|aab, B → aaBb|aab 2. None of the above. 3. S →aaBb|∊, B →aaBb|aab 4. S →aaBb|aab|∊, B →aaBb|aab

asked 2 days ago in Theory of Computation by Bhupendra (229 points) | 4 views

0 votes

0 answers

28

description of tm

asked 2 days ago in Theory of Computation by Gate Fever Junior (933 points) | 4 views

0 votes

0 answers

29

turing machine
is this halting problem thats why undecidable??

asked 2 days ago in Theory of Computation by Gate Fever Junior (933 points) | 7 views

0 votes

0 answers

30

dfa and nfa
Let M1 be a NFA with “k1” states and the corresponding DFA of M1 have “k2”states. Then which of the following option is necessarily false in every case. 1.k2 = k1 2.k2 ≤2k1 3.k2<k1 4. None of the above

asked 2 days ago in Theory of Computation by Bhupendra (229 points) | 11 views

0 votes

0 answers

31

Closure property
If L and Lc both are CFL, then L must be regular.True or False.

asked 2 days ago in Theory of Computation by Bhupendra (229 points) | 8 views

+2 votes

1 answer

32

TOC :- Number of states in DFA
Minimum number of states in DFA where:, Number of a's and Number of b's are even and epsilon is not accepted.Langugae is defined over {a,b}

answered 2 days ago in Theory of Computation by Gupta731 (273 points) | 170 views

0 votes

1 answer

33

automata
i got 124 as answer, how 3 is cfl??

answered 2 days ago in Theory of Computation by Gupta731 (273 points) | 48 views

0 votes

0 answers

34

automata
pls explain!

asked 3 days ago in Theory of Computation by Gate Fever Junior (933 points) | 25 views

0 votes

0 answers

35

automata
i am getting only 1 & 3 as answer, but my answer is incorrect!

asked 3 days ago in Theory of Computation by Gate Fever Junior (933 points) | 56 views

0 votes

0 answers

36

Turing Machine
A turing machine $\left \langle M,w,i \right \rangle$ where $M$ is TM , $w$ is string and $i$ is bit. Is the bit $i$ is encoding at last of the string $w$ or at first?

asked 3 days ago in Theory of Computation by srestha Veteran (98.3k points) | 12 views

0 votes

0 answers

37

Fermat Little Theorem(Ullman)
int exp(int i,int n){ int ans,j; ans=1; for(j=1;j<=n;j++){ ans*=i; return ans; } } main(){ int n,total,x,y,z; scanf("%d",&n); total=3; while(1){ for(x=1(;x<=total-2;x++){ for(j=1;j<=total-x-1;j++){ z=total-x-y; if(exp(x,n)+exp(y,n)==exp(z,n)) printf("Hello World"); } total++; } } } What the following code print?

asked 3 days ago in Theory of Computation by srestha Veteran (98.3k points) | 18 views

+3 votes

1 answer

38

CFL Gate 1987
Fortran is : a.Regular language b.CFL c.CSL d. None of thes Plesae tell about C, pascal and cobol also...and why?

answered 3 days ago in Theory of Computation by Rajneesh Kumar yadav (11 points) | 445 views

0 votes

0 answers

39

TOC : Minimum State in Finite Automata ( virtualgate )

asked 3 days ago in Theory of Computation by arya_stark (365 points) | 14 views

0 votes

0 answers

40

toc q
L={a$^{n}$$b^{^{n}}$ n>=0 and n $\neq$10} lang is

asked 3 days ago in Theory of Computation by amit166 (211 points) | 33 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