Dark Mode

Recent questions tagged finite-automata

2 votes

3 answers

151

Applied Test Series
Minimum number of states in the DFA of the given language ?

LRU asked in Theory of Computation Nov 2, 2021

by LRU

526 views

0 votes

1 answer

152

DFA that accepts aaa or bbb as substring-: How to make?
https://i.stack.imgur.com/v70kK.jpg I have tried but it is wrong as it accepts abba. What is the correct dfa for this?

shivajikobardan asked in Theory of Computation Nov 1, 2021

by shivajikobardan

2.4k views

3 votes

1 answer

153

Number of final states
A FA accepting language L(A) has n states and m transition. ∑ = {a, b} L(A) is given as L(A)={ x | if x ∊ L(A) then u ∊ L(A) for $∃u, v ∊ ∑^{*}$ where x=uv } Find number of final state in above DFA?

Nishisahu asked in Theory of Computation Oct 8, 2021

365 views

2 votes

3 answers

154

Regular expressons
The minimum number of states in an equivalent finite automata for the given regular expression are _____ (a(a(a(a(a(ab)*b)*b)*b)*b)*b)*

coder97 asked in Theory of Computation Oct 5, 2021

679 views

20 votes

3 answers

155

GATE CSE 2021 Set 2 | Question: 9
Let $L \subseteq \{0,1\}^*$ be an arbitrary regular language accepted by a minimal $\text{DFA}$ with $k$ states. Which one of the following languages must necessarily be accepted by a minimal $\text{DFA}$ with $k$ states? $L-\{01\}$ $L \cup \{01\}$ $\{0,1\}^* – L$ $L \cdot L$

Arjun asked in Theory of Computation Feb 18, 2021

by Arjun

9.2k views

20 votes

6 answers

156

GATE CSE 2021 Set 2 | Question: 17
Consider the following deterministic finite automaton $\text{(DFA)}$ The number of strings of length $8$ accepted by the above automaton is ___________

Arjun asked in Theory of Computation Feb 18, 2021

by Arjun

9.3k views

23 votes

3 answers

157

GATE CSE 2021 Set 2 | Question: 28
Suppose we want to design a synchronous circuit that processes a string of $0$'s and $1$'s. Given a string, it produces another string by replacing the first $1$ in any subsequence of consecutive $1$'s by a $0$ ... $\begin{array}{l} t=s+b \\ y=s \overline{b} \end{array}$

Arjun asked in Theory of Computation Feb 18, 2021

by Arjun

8.5k views

15 votes

2 answers

158

GATE CSE 2021 Set 1 | Question: 38
Consider the following language: $L= \{ w \in \{0,1\}^* \mid w \text{ ends with the substring } 011 \}$ Which one of the following deterministic finite automata accepts $L?$

Arjun asked in Theory of Computation Feb 18, 2021

by Arjun

4.2k views

2 votes

1 answer

159

NIELIT 2016 MAR Scientist C - Section C: 32
Two finite state machines are said to be equivalent if they have same number of states have same number of edges have same number of states and edges recognize same set of tokens

admin asked in Theory of Computation Apr 2, 2020

by admin

868 views

2 votes

4 answers

160

NIELIT 2017 DEC Scientific Assistant A - Section B: 3
The automaton which allows transformation to a new state without consuming any input symbols : $NFA$ $DFA$ $NFA - 1$ All of the options

admin asked in Theory of Computation Mar 31, 2020

by admin

1.6k views

2 votes

3 answers

161

NIELIT 2017 DEC Scientific Assistant A - Section B: 4
Complement of a $DFA$ can be obtained by : making starting state as final state. make final as a starting state. making final states non-final and non-final as final. None of the options

admin asked in Theory of Computation Mar 31, 2020

by admin

1.6k views

1 vote

4 answers

162

NIELIT 2017 DEC Scientific Assistant A - Section B: 5
Concatenation Operation refers to which of the following set operations : Union Dot Kleene None of the options

admin asked in Theory of Computation Mar 31, 2020

by admin

3.6k views

1 vote

2 answers

163

NIELIT 2017 DEC Scientific Assistant A - Section B: 31
A finite automaton accepts which type of language : Type $0$ Type $1$ Type $2$ Type $3$

admin asked in Theory of Computation Mar 31, 2020

by admin

3.3k views

1 vote

2 answers

164

NIELIT 2017 DEC Scientific Assistant A - Section B: 40
What is the relation between $DFA$ and $NFA$ on the basis of computational power ? $DFA$ > $NFA$ $NFA$ > $DFA$ Equal Can't be said

admin asked in Theory of Computation Mar 31, 2020

by admin

999 views

1 vote

1 answer

165

NIELIT 2017 DEC Scientific Assistant A - Section B: 50
How many DFA's exits with two states over input alphabet $\left \{ 0,1 \right \}$ $16$ $26$ $32$ $64$

admin asked in Theory of Computation Mar 31, 2020

by admin

992 views

2 votes

2 answers

166

NIELIT 2017 DEC Scientific Assistant A - Section B: 60
Finite automata requires minimum ____________ number of stacks. $1$ $0$ $2$ None of the options

admin asked in Theory of Computation Mar 31, 2020

by admin

3.7k views

3 votes

3 answers

167

NIELIT 2016 DEC Scientist B (CS) - Section B: 1
Palindromes can't be recognized by any Finite State Automata because: FSA cannot remember arbitrarily large amount of information. FSA cannot deterministically fix the midpoint. Even if the mid-Point is known an FSA cannot find whether the second half of the string matches the first half. All of the above.

admin asked in Theory of Computation Mar 31, 2020

by admin

12.1k views

2 votes

2 answers

168

NIELIT 2016 DEC Scientist B (CS) - Section B: 24
Given two DFA's $M1$ and $M2$. They are equivalent if $M1$ and $M2$ has the same number of states $M1$ and $M2$ accepts the same language i.e $L(M1)=L(M2)$ $M1$ and $M2$ has the same number of final states None of the above

admin asked in Theory of Computation Mar 31, 2020

by admin

1.5k views

3 votes

2 answers

169

NIELIT 2016 DEC Scientist B (CS) - Section B: 46
$(00+01+10)(0+1)^*$ represents Strings not starting with $11$ Strings of odd length Strings starting with $00$ Strings of even length

admin asked in Theory of Computation Mar 31, 2020

by admin

1.1k views

1 vote

1 answer

170

NIELIT 2017 July Scientist B (CS) - Section B: 48
What is the complement of the language accepted by the NFA shown below? $\not{O}$ $\{\epsilon\}$ $a^*$ $\{a,\epsilon\}$ $1$ $2$ $3$ $4$

admin asked in Theory of Computation Mar 30, 2020

by admin

874 views

0 votes

6 answers

171

NIELIT 2017 DEC Scientist B - Section B: 39
Which of the following is true? Mealy and Moore machine are language acceptors. Finite State automata is language translator. NPDA is more powerful than DPDA. Melay machine is more powerful than Moore machine.

admin asked in Theory of Computation Mar 30, 2020

by admin

5.9k views

7 votes

5 answers

172

ISRO2020-41
Minimum number of states required in DFA accepting binary strings not ending in $\text{“101”}$ is $3$ $4$ $5$ $6$

Satbir asked in Theory of Computation Jan 13, 2020

by Satbir

7.0k views

Page:

« prev
1
2
3
4
5
6
7
8
9
10
11
...
35
next »

Recent questions tagged finite-automata