Dark Mode

Recent questions tagged theory-of-computation

0 votes

0 answers

1

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

practicalmetal asked in Theory of Computation 1 hour ago

by practicalmetal

6 views

0 votes

0 answers

2

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

practicalmetal asked in Theory of Computation 1 hour ago

by practicalmetal

6 views

0 votes

1 answer

3

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.

practicalmetal asked in Theory of Computation 5 days ago

by practicalmetal

65 views

6 votes

2 answers

4

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)^{*}$

admin asked in Theory of Computation Feb 15

by admin

1.2k views

3 votes

4 answers

5

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)

admin asked in Theory of Computation Feb 15

by admin

1.0k views

2 votes

3 answers

6

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.

admin asked in Theory of Computation Feb 15

by admin

932 views

4 votes

2 answers

7

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

admin asked in Theory of Computation Feb 15

by admin

928 views

2 votes

2 answers

8

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

admin asked in Theory of Computation Feb 15

by admin

822 views

2 votes

4 answers

9

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 ____________.

admin asked in Theory of Computation Feb 15

by admin

913 views

0 votes

0 answers

10

#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

82 views

0 votes

0 answers

11

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

99 views

0 votes

0 answers

12

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

178 views

0 votes

0 answers

13

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

123 views

0 votes

0 answers

14

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) ∗ ).

Silver_Reaper asked in Theory of Computation Feb 6

by Silver_Reaper

122 views

1 vote

2 answers

15

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)^*$

GO Classes asked in Theory of Computation Feb 6

427 views

2 votes

0 answers

16

Can DCFL be ambiguous?
Can DCFL be ambiguous?

h4kr asked in Theory of Computation Feb 2

by h4kr

134 views

0 votes

1 answer

17

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.

Silver_Reaper asked in Theory of Computation Jan 28

by Silver_Reaper

111 views

0 votes

2 answers

18

TOC | Made Easy mock

abhinowKatore asked in Theory of Computation Jan 24

by abhinowKatore

138 views

0 votes

0 answers

19

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

74 views

0 votes

1 answer

20

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

90 views

0 votes

0 answers

21

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

84 views

Page:

1
2
3
4
5
6
...
148
next »

Recent questions tagged theory-of-computation