Dark Mode

Recent questions tagged minimal-state-automata

2 votes

4 answers

1

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

1 answer

2

Minimum number of states

Dknights asked in Theory of Computation Jan 12

62 views

0 votes

1 answer

3

Construct pushdown automata that recognize the following language. L= (a²ⁿ b³ⁿ | n ≥ 0}
Construct pushdown automata that recognize the following language. L= (a²ⁿ b³ⁿ | n ≥ 0}

M_Umair_Khan42900 asked in Theory of Computation Dec 29, 2022

by M_Umair_Khan42900

76 views

0 votes

1 answer

4

Write regular expression to denote a language L a) String which begin or end with either 00 or 11. b) The set of all strings, when viewed as binary representation of integers, that are divisible by 2. c) The set of all strings containing 00. d) String not containing the substring 110.

M_Umair_Khan42900 asked in Theory of Computation Dec 29, 2022

by M_Umair_Khan42900

123 views

2 votes

0 answers

5

h4kr asked in Theory of Computation Nov 18, 2022

by h4kr

88 views

1 vote

1 answer

6

Test-Series
Consider the following language over $\sum$ = {0, 1} L = {w | w $\epsilon \sum$ * and |w| is divisible by 2 and not by 4} How many sates will min-DFA accepting L will have?

Pranavpurkar asked in Theory of Computation Nov 11, 2022

by Pranavpurkar

154 views

0 votes

2 answers

7

How to do questions of ToC like finding min. No. Of states , min. No. Of substring etc ?

Ferox asked in Theory of Computation Oct 10, 2022

by Ferox

136 views

0 votes

0 answers

8

How to practice ToC precisely ? Like I am unable to know transitions for intermediate states in dfa design , it takes time and sometimes I am unable to answer !! Ex – Σ ={a,b} design dfa for : 1.exactly 2a and 2b 2. Minimum 2a and minimum 2b In these thinking about intermediate transitions for possible acceptable strings takes time and sometimes i get wrong answer !!! So what to do to get exact accurate answer with min. Of states in such type of ques. ?

Ferox asked in Theory of Computation Oct 10, 2022

by Ferox

74 views

1 vote

1 answer

9

Theory of Computation
Steps to find the answer?

Overflow04 asked in Theory of Computation Jul 16, 2022

220 views

0 votes

0 answers

10

Minimal DFA
What will be the minimal DFA for $\left \{a^{n} :n mod 3 =0 \right \}\cup \left \{a^{n} :n mod 5 =1 \right \}$

ankit-saha asked in Theory of Computation Mar 24, 2022

190 views

0 votes

1 answer

11

MADE EASY 2022 Work book -Theory of Computation series
Let L be a regular language on alphabet Σ. The union of the myhill-nerode equivalence classes is always _____, and the pairwise intersection of the myhill-nerode equivalence classes is always Fill up the blanks

abhinowKatore asked in Theory of Computation Mar 7, 2022

by abhinowKatore

161 views

0 votes

1 answer

12

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

1.0k views

3 votes

1 answer

13

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

248 views

4 votes

2 answers

14

UGC NET CSE | June 2019 | Part 2 | Question: 75
How many states are there in a minimum state automata equivalent to regular expression given below? Regular expression is $a^*b(a+b)$ $1$ $2$ $3$ $4$

Arjun asked in Theory of Computation Jul 2, 2019

by Arjun

3.5k views

42 votes

5 answers

15

GATE CSE 2019 | Question: 48
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$ ... Consider the language $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______

Arjun asked in Theory of Computation Feb 7, 2019

by Arjun

15.7k views

0 votes

1 answer

16

Self Doubt
Find the minimum number of states in the DFA which accept the language of all strings that begin or end with 00 or 11.

kumar.dilip asked in Theory of Computation Jan 19, 2019

487 views

1 vote

1 answer

17

Applied Course | Mock GATE | Test 1 | Question: 44
Minimum number of states in a deterministic Finite automata that accepts the given language is ______ $L = \{ w \mid w \text{ is any string not in } a^*b^* \}$

Applied Course asked in Theory of Computation Jan 16, 2019

by Applied Course

430 views

Page:

1
2
3
4
5
6
7
next »

Recent questions tagged minimal-state-automata