Dark Mode

Recent questions and answers in Theory of Computation

0 votes

2 answers

1

Regular expression
is a(ba)*=(ab)*a?

kumar123 answered in Theory of Computation 5 days ago

80 views

0 votes

1 answer

2

Peter Linz Edition 5 Exercise 12.1 Question 9 (Page No. 308)
$\text{Definition:}\space$A pushdown automaton $M = (Q,\Sigma,\Gamma,\delta,q_0,z,F)$ ... that is, given a pda as in Definition, can we always predict whether or not the automaton will halt on input $w?$

iselfraja answered in Theory of Computation 6 days ago

157 views

0 votes

1 answer

3

Building a pushdown automata that receives L*
given a pushdown automata that receives L by getting to an accepting state, how can a pushdown automata be built, so that it accepts L*? (might use a “double bottom” if needed)?? i don’t know how to solve it and would appreciate any kind of help! studying for exam and must learn how to solve it

Ratul Chatterjee answered in Theory of Computation 6 days ago

by Ratul Chatterjee

178 views

0 votes

1 answer

4

selfdoubt
if concatenation of two languages $L_1\ and\ L_2(L_1.L_2)$ is regular then what can we say about $L_1\ and\ L_2 $ ?? is there any possibility of $L_1=nonregular\ ,\ L_2=nonregular \ $ ??

manikantsharma answered in Theory of Computation Sep 23

by manikantsharma

557 views

0 votes

0 answers

5

GATE CSE 2020
Is this language a regular language ? If yes why and if No why ? The last part is “x!=y” cropped in the picture According to my understanding this is not regular because its says number of x = number of y But Finite automata cant compare the number of x and y here with limited memory. Can you please explain ?

dutta18 asked in Theory of Computation Sep 22

66 views

11 votes

4 answers

6

GATE CSE 2020 | Question: 51
Consider the following language. $L = \{{ x\in \{a,b\}^*\mid}$number of $a$’s in $x$ divisible by $2$ but not divisible by $3\}$ The minimum number of states in DFA that accepts $L$ is _________

dutta18 answered in Theory of Computation Sep 22

8.2k views

0 votes

0 answers

7

Regular expression
Can we simplify a*+a*b(d+ca*b)*ca* ? Where a,b,c,d are regular expression.

nbhatt asked in Theory of Computation Sep 21

by nbhatt

57 views

0 votes

1 answer

8

Regular expression
What will be the regular expression for following fa using recurrence relation method.

Nisha Bharti answered in Theory of Computation Sep 21

by Nisha Bharti

57 views

0 votes

1 answer

9

Conversion of Regular expression to Finite Automata
What is the Finite Automata( NFA, epsilon-NFA or DFA) for the regular expression (a*ba)* ?

Sumit Singh Dhami answered in Theory of Computation Sep 21

by Sumit Singh Dhami

52 views

13 votes

4 answers

10

GATE CSE 2022 | Question: 2
Which one of the following regular expressions correctly represents the language of the finite automaton given below? $ab^{\ast}bab^{\ast} + ba^{\ast}aba^{\ast}$ $(ab^{\ast}b)^{\ast}ab^{\ast} + (ba^{\ast}a)^{\ast} ba^{\ast}$ $(ab^{\ast}b + ba^{\ast}a)^{\ast} (a^{\ast} + b^{\ast})$ $(ba^{\ast}a + ab^{\ast}b)^{\ast} (ab^{\ast} + ba^{\ast})$

Prateek pallaw answered in Theory of Computation Sep 19

by Prateek pallaw

3.1k views

0 votes

1 answer

11

PhD Qualifier Examination, Paper I
Give a context-free grammar for the set of all strings over the alphabet {a, b} with exactly twice as many a’s as b’s. Explain the working of the grammar by characterizing the strings generated by each non-terminal.

afroze answered in Theory of Computation Sep 17

by afroze

43 views

60 votes

4 answers

12

GATE CSE 2008 | Question: 51
Match the following: $\small{\begin{array}{|ll|ll|}\hline \text{E.} & \text{Checking that identifiers are declared before their use} & \text{P.} & \text{$L \: = \: \left\{a^nb^mc^nd^m \mid n\: \geq1, m \geq 1\right\}$} \\\hline \text{F.} & \text{Number of formal ... $\text{E-R, F-P, G-Q, H-S}$ $\text{E-P, F-R, G-S, H-Q}$

Deepak Poonia answered in Theory of Computation Sep 17

by Deepak Poonia

10.9k views

0 votes

1 answer

13

LRU answered in Theory of Computation Sep 16

by LRU

52 views

1 vote

1 answer

14

Turing Machine Rice's Theorem
L = {M|M is a TM that accepts all even numbers} For the above language i can have Tyes machine which has all even numbers.And Tno as machine whose language is empty.So i can say it is undecidable. But to show it is Not RE. What ... am assuming here that the property of the language as "Only all even numbers",i guess the same has been given in the question.

manikantsharma answered in Theory of Computation Sep 16

by manikantsharma

672 views

0 votes

1 answer

15

Rice's Theorem
Example# 3 from Part-1 Rice's Theorem from https://gatecse.in/rices-theorem/ states as follows (3) L(M) is recognized by a TM having even number of states Sol: This is a trivial property. This set equals the set of recursively enumerable languages. According to ... then? Can someone give me an example for which TYES and TNO cannot be found and let me know if my approach is correct ?

manikantsharma answered in Theory of Computation Sep 16

by manikantsharma

502 views

1 vote

3 answers

16

Regular expression
Is (a+ab*b)* and (ab*)* same or not?

Hira Thakur answered in Theory of Computation Sep 16

198 views

5 votes

1 answer

17

GATE CSE 1988 | Question: 15
Consider the DFA $M$ and NFA $M_{2}$ as defined below. Let the language accepted by machine $M$ be $L$. What language machine $M_{2}$ accepts, if $F2=A?$ $F2=B?$ $F2=C?$ $F2=D?$ $M=(Q, \Sigma, \delta, q_0, F)$ $M_{2}=(Q2, \Sigma, \delta_2, q_{00}, F2)$ ... $D=\{\langle p, q, r \rangle \mid p,q \in Q; r \in F\}$

Deepak Poonia answered in Theory of Computation Sep 15

by Deepak Poonia

1.2k views

0 votes

0 answers

18

Closure Properties of Languages
Doubt 1: CFL $\cap$ DCFL = CFL CFL - Context Free Languages DCFL - Deterministic Context Free Languages Can you prove above expression Doubt 2: Consider L$_{1}$ = Language generated by a machine M1 L$_{2}$ = Language ... TM Doubt 3: Non Recursively Enumerable Language $\cap$ Any language = Non Recursively Enumerable Language Is this statement correct/always true?

Chaitanya Kale asked in Theory of Computation Sep 4

by Chaitanya Kale

103 views

2 votes

2 answers

19

ACE ACADEMY: TOC
How many 2 state DFA’s with designated initial state can be constructed over the alphabet Σ = {a, b} that accept empty language ϕ ? (a) 4 (b) 16 (c) 20 (d) 24

[ Jiren ] answered in Theory of Computation Sep 4

1.5k views

0 votes

2 answers

20

Identification of Regular Language | TOC | Practice Question | Unacademy Class
Which of the following is/are Regular? A] $\left \{ XWYW^{R} \space\ | \space\ W,X,Y \in \left \{ a,b \right \}^{+} \right \}$ ... D] None R => Reverse Please describe your answer.

Srken answered in Theory of Computation Sep 4

by Srken

168 views

0 votes

0 answers

21

#Toc #regularexpression
How to convert (a+b)* into a minimal Dfa

Srken asked in Theory of Computation Sep 4

by Srken

71 views

0 votes

0 answers

22

Self query
What book should i refer to understand the toc problems i just understand the basics of toc but not be able to solve the problem of toc and cd plz anyone suggest me what book should i follow even after saw the full playlist of toc i am not be able to solve the basic basic problems plz anyone suggest me something To make my toc and cd concept strong

Vaishnavi Gadhe asked in Theory of Computation Sep 3

by Vaishnavi Gadhe

57 views

0 votes

0 answers

23

PDA | TOC | Practice Question
Identify the type of the given language and draw the corresponding automata for the language. $L=\left \{a^{i}b^{j}c^{k} \space\ | \space\ j=max(i,k) \right \}$ A] Regular B] DCFL C] CFL but not DCFL D] Non-CFL Please describe your selection.

anupamsworld asked in Theory of Computation Sep 2

by anupamsworld

72 views

0 votes

0 answers

24

PDA | TOC | Practice Question | Unacademy Class
Construct PDA using empty stack method for the given language. $L=\left \{ x \space\ | \space\ x\in \left \{ a,b \right \}^{*} ; n_{a}(x) >= n_{b}(x) \right \}$ //number of a’s is greater than or equal to number of b’s

anupamsworld asked in Theory of Computation Sep 1

by anupamsworld

45 views

1 vote

1 answer

25

Peter Linz Edition 4 Exercise 1.2 Question 10 (Page No. 28)
Prove or disprove the following claims. (a) $(L_1 ∪ L_2)^R = L_1^R ∪ L_2^R$ for all languages $L_1$ and $L_2$. (b) $(L^R)^* = (L^*)^R$ for all languages $L$.

Deepak Poonia answered in Theory of Computation Aug 30

by Deepak Poonia

189 views

1 vote

1 answer

26

Peter Linz Edition 4 Exercise 1.2 Question 8 (Page No. 28)
Prove that $(L_1L_2)^R=L_2^RL_1^R$ for all languages $L_1$ and $L_2$.

Deepak Poonia answered in Theory of Computation Aug 30

by Deepak Poonia

133 views

20 votes

6 answers

27

GATE CSE 1996 | Question: 2.8
If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one? $L_1.L_2$ $L_1 \cap L_2$ $L_1 \cap R$ $L_1 \cup L_2$

manikantsharma answered in Theory of Computation Aug 27

by manikantsharma

4.7k views

29 votes

8 answers

28

GATE CSE 1995 | Question: 2.20
Which of the following definitions below generate the same language as $L$, where $L=\{x^ny^n \text{ such that } n\geq 1 \}$? $E \rightarrow xEy\mid xy$ $x y \mid (x^+xyy^+$) $x^+y^+$ I only I and II II and III II only

manikantsharma answered in Theory of Computation Aug 27

by manikantsharma

8.2k views

20 votes

4 answers

29

GATE CSE 1992 | Question: 02,xix
Context-free languages are: closed under union closed under complementation closed under intersection closed under Kleene closure

manikantsharma answered in Theory of Computation Aug 27

by manikantsharma

3.4k views

19 votes

4 answers

30

GATE CSE 1987 | Question: 2k
State whether the following statements are TRUE or FALSE: The intersection of two CFL's is also a CFL.

manikantsharma answered in Theory of Computation Aug 27

by manikantsharma

2.2k views

36 votes

9 answers

31

GATE CSE 1991 | Question: 17,b
Let $L$ be the language of all binary strings in which the third symbol from the right is a $1$. Give a non-deterministic finite automaton that recognizes $L$. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?

yuyutsu answered in Theory of Computation Aug 25

9.0k views

1 vote

2 answers

32

Properties of regular expression | TOC | Doubt
1] ∅^* = ? 2] ∅^+ = ? 3] ∅ . ∈ = ? please describe your answers.

abhinowKatore answered in Theory of Computation Aug 23

by abhinowKatore

197 views

38 votes

6 answers

33

GATE CSE 2012 | Question: 24
Which of the following problems are decidable? Does a given program ever produce an output? If $L$ is a context-free language, then, is $\bar{L}$ also context-free? If $L$ is a regular language, then, is $\bar{L}$ also regular? If $L$ is a recursive language, then, is $\bar{L}$ also recursive? $1, 2, 3, 4$ $1, 2$ $2, 3, 4$ $3, 4$

gvinay answered in Theory of Computation Aug 22

by gvinay

12.5k views

52 votes

11 answers

34

GATE CSE 2003 | Question: 14
The regular expression $0^*(10^*)^*$ denotes the same set as $(1^*0)^*1^*$ $0+(0+10)^*$ $(0+1)^*10(0+1)^*$ None of the above

manikantsharma answered in Theory of Computation Aug 20

by manikantsharma

13.8k views

24 votes

4 answers

35

GATE CSE 2000 | Question: 1.4
Let $S$ and $T$ be languages over $\Sigma=\{a,b\}$ represented by the regular expressions $(a+b^*)^*$ and $(a+b)^*$, respectively. Which of the following is true? $S \subset T$ $T \subset S$ $S = T$ $S \cap T = \phi$

manikantsharma answered in Theory of Computation Aug 20

by manikantsharma

9.3k views

35 votes

4 answers

36

GATE CSE 1998 | Question: 1.9
If the regular set $A$ is represented by $A = (01 + 1)^*$ and the regular set $B$ is represented by $B = \left(\left(01\right)^*1^*\right)^*$, which of the following is true? $A \subset B$ $B \subset A$ $A$ and $B$ are incomparable $A = B$

manikantsharma answered in Theory of Computation Aug 20

by manikantsharma

8.9k views

0 votes

1 answer

37

Gate cse
Can we construct finite automata for The numbers 1,2,4...2^n,.... Written in unary

pranita-parab asked in Theory of Computation Aug 14

by pranita-parab

110 views

0 votes

1 answer

38

Construct a grammar which generates all odd integers up to 999

clendaya asked in Theory of Computation Aug 11

82 views

0 votes

0 answers

39

TOC doubt
How a language which is not recursively enumerable is uncountable,because as we know every language is a subset of sigma(input alphabet) star which is known to be countable? Please explain I am getting confused in this.

Himanshu555 asked in Theory of Computation Aug 5

55 views

0 votes

1 answer

40

Self Doubt
$L=\{wa^nw^Rb^n\mid w\in \left \{ a,b \right \}^\ast ,n\geqslant 0\}$ Can anyone give me step by step solution that shows this is not CFL by pumping Lemma?

tusharb asked in Theory of Computation Jul 29

123 views

To see more, click for all the questions in this category.

Recent questions and answers in Theory of Computation