Dark Mode

Recent questions and answers in Theory of Computation

0 votes

0 answers

1

Regular Languages
The solution to $X = r +Xs$ by Arden’s Lemma when s has ϵ a) an infinite number of solutions b) a finite number of solutions c) is always unique d) none

practicalmetal asked in Theory of Computation 3 days ago

by practicalmetal

20 views

0 votes

1 answer

2

Context Free Languages
Is the following language CFL : { ww | w in (a+b)* and |w| <1000 }

himalay answered in Theory of Computation 3 days ago

55 views

0 votes

1 answer

3

Context Free Language
The complement of the languages: i) {ww | w in (0+1)*} ii) {$a^n b^nc^n$ | n>1} are a) Context Free b) Not Context Free c)are DCFL’s d)None

deathWalker answered in Theory of Computation 6 days ago

57 views

0 votes

1 answer

4

Context Free Languages
Is the following language context free: The set of all strings with number of a’s equal to number of b’s and the sum of a’s and b’s to be divisible by 3.

GNANESWARA SAI answered in Theory of Computation Mar 16

by GNANESWARA SAI

85 views

0 votes

4 answers

5

TOC
What are the number of states needed in minimal DFA, that accepts (1+1111)* A. 5 B. 4 C. 1 D. None

Bharat Bhushan answered in Theory of Computation Mar 10

by Bharat Bhushan

2.9k views

18 votes

3 answers

6

How to construct an automata with even number of a's and odd number of b's?
The alphabets are a and b. Construct a DFA

Bharat Bhushan answered in Theory of Computation Mar 5

by Bharat Bhushan

81.1k views

1 vote

2 answers

7

Peter Linz Edition 4 Exercise 3.1 Question 12 (Page No. 76)
Find a regular expression for the complement of the language in $L (r) =$ {$a^{2n}b^{2m+1}: n ≥ 0, m ≥ 0$}.

Genius answered in Theory of Computation Mar 4

by Genius

225 views

0 votes

2 answers

8

context free grammar
what is the langauge generated by this grammar ? S-->aS | aSbS | ε what is the language

KG answered in Theory of Computation Mar 2

by KG

80 views

8 votes

2 answers

9

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\}$

Genius answered in Theory of Computation Feb 26

by Genius

1.6k views

1 vote

1 answer

10

Peter Linz Edition 4 Exercise 3.1 Question 17 (Page No. 76)
Write regular expressions for the following languages on {$0, 1$}. (a) all strings ending in $01$, (b) all strings not ending in $01$, (c) all strings containing an even number of $0$'s, (d) Peter Linz Edition 4 ... (e) all strings with at most two occurrences of the substring $00$, (f) all strings not containing the substring $101$.

Harsh Saini_1 answered in Theory of Computation Feb 25

by Harsh Saini_1

368 views

2 votes

3 answers

11

Peter Linz Edition 4 Exercise 3.1 Question 16.d (Page No. 76)
Find a regular expression over Σ ={a,b,c} for all strings that contain no run of a's of length greater than 2. Here a run in a string is a sub string of length at least two as long as possible and consisting entirely of the same symbol. For eg, the string abbbaab contains a run of b's of length three and a tun of a's of length two.

Harsh Saini_1 answered in Theory of Computation Feb 24

by Harsh Saini_1

2.0k views

1 vote

1 answer

12

Peter Linz Edition 4 Exercise 3.1 Question 15 (Page No. 76)
Find a regular expression for $L =$ {$w∈ $ {$0,1$}$^* : w$ has exactly one pair of consecutive zeros} .

Harsh Saini_1 answered in Theory of Computation Feb 24

by Harsh Saini_1

192 views

1 vote

1 answer

13

Peter Linz Edition 4 Exercise 3.1 Question 13 (Page No. 76)
Find a regular expression for $L =$ {$vwv: v, w ∈${$a, b$}$^*, |v| =2$}.

Harsh Saini_1 answered in Theory of Computation Feb 23

by Harsh Saini_1

143 views

1 vote

1 answer

14

Peter Linz Edition 4 Exercise 3.1 Question 11 (Page No. 76)
Find a regular expression for $L =$ {$ab^nw: n ≥ 3, w ∈$ {$a, b$}$^+$}.

Harsh Saini_1 answered in Theory of Computation Feb 23

by Harsh Saini_1

153 views

2 votes

3 answers

15

GATE CSE 2023 | Question: 14
Which of the following statements is/are $\text{CORRECT}?$ The intersection of two regular languages is regular. The intersection of two context-free languages is context-free. The intersection of two recursive languages is recursive. The intersection of two recursively enumerable languages is recursively enumerable.

Hira Thakur answered in Theory of Computation Feb 16

993 views

6 votes

2 answers

16

GATE CSE 2023 | Question: 4
Consider the Deterministic Finite-state Automaton ($\text{DFA}$) $\mathcal{A}$ shown below. The $\text{DFA}$ runs on the alphabet $\{0,1\}$, and has the set of states $\{s, p, q, r\}$, with $s$ being the start state and $p$ being the only final state. Which one of the following ... $1\left(0^{*} 11\right)^{*}$ $0(0+1)^{*}$ $1(0+11)^{*}$ $1\left(110^{*}\right)^{*}$

Hira Thakur answered in Theory of Computation Feb 16

1.3k views

0 votes

0 answers

17

Gate 2023
Consider the language L over the alphabet {0, 1}, given below: L = {w ∈ {0, 1}* | w does not contain three or more consecutive 1’s}. The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is ______ . closed

ic3rror asked in Theory of Computation Feb 16

351 views

3 votes

4 answers

18

GATE CSE 2023 | Question: 9
Consider the following definition of a lexical token $\textbf{id}$ for an identifier in a programming language, using extended regular expressions: \[ \begin{array}{ll} \textbf{ letter } & \rightarrow[\mathrm{A}-\mathrm{Za}-\mathrm{ ... Finite-state Automata with $\epsilon$-transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

Hira Thakur answered in Theory of Computation Feb 16

1.1k views

2 votes

4 answers

19

GATE CSE 2023 | Question: 53
Consider the language $L$ over the alphabet $\{0,1\}$, given below: \[ L=\left\{w \in\{0,1\}^{*} \mid w \text { does not contain three or more consecutive } 1 \text { 's }\right\} . \] The minimum number of states in a Deterministic Finite-State Automaton $\text{(DFA)}$ for $L$ is ____________.

Hira Thakur answered in Theory of Computation Feb 16

977 views

4 votes

2 answers

20

GATE CSE 2023 | Question: 29
Consider the context-free grammar $G$ below \[ \begin{array}{l} S \rightarrow a S b \mid X \\ X \rightarrow a X \mid X b \mid a \mid b, \end{array} \] where $S$ and $X$ are non-terminals, and $a$ and $b$ are terminal symbols. The starting non- ... $G$ is $a^{\ast} b^{\ast}(a+b)$ The language generated by $G$ is not a regular language

Deepak Poonia answered in Theory of Computation Feb 15

by Deepak Poonia

999 views

2 votes

2 answers

21

GATE CSE 2023 | Question: 30
Consider the pushdown automaton $\text{(PDA)}\;P$ below, which runs on the input alphabet $\{a, b\}$, has stack alphabet $\{\perp, A\}$, and has three states $\{s, p, q\}$, with $s$ being the start state. A transition from state $u$ to state $v$ ... $\left.0 \leq n\right\}$ $\left\{a^{m} \mid 0 \leq m\right\} \cup\left\{b^{n} \mid 0 \leq n\right\}$

Deepak Poonia answered in Theory of Computation Feb 15

by Deepak Poonia

867 views

0 votes

0 answers

22

#TIFR
Consider the language $L = \{a^i \$ a^j \$ b^k \$ | k ⩽ max(i, j), i, j, k ≥ 0\}$ over the alphabet $\sum = \{a, b, \$ \}$. The complement of the language L, that is, $\sum^* - \text{ L}$ is denoted by $L'$. Which of the following is ... d) $L$ is a context-free language and $L'$ is not a context-free language. (e) Neither is $L$ a context-free language nor is $L'$ a context-free language.

amit166 asked in Theory of Computation Feb 13

85 views

0 votes

0 answers

23

Peter Linz Edition 5 Exercise 10.5 Question 3
Consider an offline Turing machine in which the input can be read only once, moving left to right, and not rewritten. On its work tape, it can use at most n extra cells for work space, where n is fixed for all inputs. Show that such a machine is equivalent to a finite automaton.

borhanElmi asked in Theory of Computation Feb 9

101 views

0 votes

0 answers

24

Isi Kolkata 2022
Prove or disprove the following statements: (i) L1 = {0^i1^j | i, j ∈ N} is a regular language. (ii) L2 = {0^n1^n | n ∈ N} is a regular language. (iii) For x ∈ {0, 1}*, R(x) denotes the string obtained by reversing the string x. C(x) denotes the string ... 0 in the string x. L3 = {x ∈ {0, 1}* | x = R (C (x))} is a regular language. How to solve this in subjective way..

devilstephen7 asked in Theory of Computation Feb 8

by devilstephen7

182 views

0 votes

0 answers

25

Computational Theory
Give the state diagram of DFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0, 1}. {w | accept all string except 11 or 110} {w | w begins with a 11 and ends with a 0} {w | All string accepted except ... w | w contains at least three 0s } { w | w contains the substring 0101, i.e., w = x0101y for some x and y }

ahmed5 asked in Theory of Computation Feb 8

by ahmed5

128 views

0 votes

2 answers

26

Peter Linz Edition 4 Exercise 1.2 Question 12 (Page No. 28)
Give a simple description of the language generated by the grammar with productions $S \rightarrow aA,$ $A \rightarrow bS,$ $S \rightarrow λ.$

Hira Thakur answered in Theory of Computation Feb 6

255 views

0 votes

1 answer

27

Peter Linz Edition 4 Exercise 3.1 Question 26 (Page No. 77)
Find an nfa that accepts the language $L (aa^* (a + b))$.

Hira Thakur answered in Theory of Computation Feb 6

172 views

0 votes

1 answer

28

Peter Linz Edition 4 Exercise 3.2 Question 1 (Page No. 87)
Find an nfa that accepts the language $L (ab^*aa + bba^*ab)$.

Hira Thakur answered in Theory of Computation Feb 6

96 views

1 vote

2 answers

29

Peter Linz Edition 4 Exercise 3.1 Question 1 (Page No. 75)
Find all strings in $L((a + b) b (a + ab)^*)$ of length less than four.

Hira Thakur answered in Theory of Computation Feb 6

378 views

0 votes

0 answers

30

An Introduction to Formal Languages and Automata,Peter Linz,6th edition,exercise 3.3 q3
Find a regular grammar that generates the language L (aa ∗ (ab + a) ∗ ). closed

Silver_Reaper asked in Theory of Computation Feb 6

by Silver_Reaper

129 views

1 vote

2 answers

31

GATE CSE 2023 | Memory Based Question: 25
Consider the following finite automata and find the correct regular expression. $0(0+11)^*$ $1(0+11)^*$ $1(0 * 11)^*$ $0\left(0^* 11\right)^*$ closed

Hira Thakur answered in Theory of Computation Feb 6

440 views

2 votes

0 answers

32

Can DCFL be ambiguous?
Can DCFL be ambiguous?

h4kr asked in Theory of Computation Feb 2

by h4kr

137 views

0 votes

3 answers

33

For any language, if the union of both is regular, then are those languages regular languages as well?

abhinowKatore answered in Theory of Computation Feb 1

by abhinowKatore

470 views

0 votes

1 answer

34

An Introduction to Formal Languages and Automata,6th edition,Exercise 2.3 Q2.
Convert the nfa in Exercise 13, Section 2.2, into an equivalent dfa.

Pranavpurkar answered in Theory of Computation Jan 30

by Pranavpurkar

129 views

0 votes

1 answer

35

#gate questions
which one true 1. Determining whether context-free grammar is un-decidable 2. Whether a given grammar is context-free is decidable

elsar martin answered in Theory of Computation Jan 30

by elsar martin

96 views

0 votes

2 answers

36

TOC | Made Easy mock

Vijay_Ram answered in Theory of Computation Jan 28

142 views

0 votes

0 answers

37

An Introduction to Formal Languages and Automata Peter Linz 6th Edition.Exercise 2.1 4 d,e
For Σ = {a, b}, construct dfa’s that accept the sets consisting of: (d) all strings with at least one b and exactly two a’s. (e) all the strings with exactly two a’s and more than three b’s.

Silver_Reaper asked in Theory of Computation Jan 24

by Silver_Reaper

81 views

0 votes

1 answer

38

Self Doubt
Consider L is recursive language and G is Recursively Enumerable then, L' union G is Recursively enumerable. Can someone please explain me this statement why it is true.?

TusharKumar asked in Theory of Computation Jan 21

94 views

0 votes

0 answers

39

Made Easy Gate Mock -1
Let L be a language over {a,b} that contains the same number of occurrences of a and b. which of the following is non-regular? a. b. c. d. MSQ & answer is a,c,d

TusharKumar asked in Theory of Computation Jan 21

92 views

0 votes

0 answers

40

derive a language from a grammar
{M ∈ {a,b}∗ | M contains at least three bs} {N ∈ {a,b}∗ | N has an odd length and a is in the middle always}

moe12leb asked in Theory of Computation Jan 21

64 views

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

Recent questions and answers in Theory of Computation