Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Some useful problems
Recent questions tagged finite-automata
120
views
1
answers
0
votes
DFA construction
Design a DFA to recognize all strings over {a,b} such that L={awa : w ϵ {a,b}* }.
Design a DFA to recognize all strings over {a,b} such that L={awa : w ϵ {a,b}* }.
Unnati Singh
Unnati Singh
asked
May 7
Theory of Computation
theory-of-computation
finite-automata
+
–
142
views
2
answers
0
votes
DFA construction
Construct a DFA with minimum number of states, accepting all strings over {a, b} such that the number of a’s is divisible by three and the number of b’s is divisible by two.
Construct a DFA with minimum number of states, accepting all strings over {a, b} such that the number of a’s is divisible by three and the number of b’s is divisible ...
Unnati Singh
Unnati Singh
asked
May 7
Theory of Computation
theory-of-computation
finite-automata
+
–
139
views
1
answers
0
votes
DFA construction
Design a DFA (Deterministic Finite Automaton) that recognizes the language L defined follows: L= {w -> {a, b}* | every a in w is immediately followed by bb}
Design a DFA (Deterministic Finite Automaton) that recognizes the language L defined follows: L= {w - {a, b}* | every a in w is immediately followed by bb}
rdrd44
rdrd44
asked
May 3
Theory of Computation
theory-of-computation
finite-automata
+
–
100
views
0
answers
0
votes
Regular Expresssion And NFA
In certain programming languages, comments appear between delimiters such as (* and ) . Let C be the language of all valid delimited comment strings. Such a string in C must begin with ( and end with *) but have no intervening *) . For simplicity, assume the ... b, (, *)}. (a) Provide an NFA that recognizes language C . (b) Present a regular expression that generates C.
In certain programming languages, comments appear between delimiters such as (* and ) . Let C be the language of all valid delimited comment strings. Such a string in C...
rdrd44
rdrd44
asked
May 3
Theory of Computation
theory-of-computation
regular-expression
finite-automata
+
–
129
views
0
answers
1
votes
How is "All strings {0,1} of length five or more in which the third symbol from the right end is different from the leftmost symbol" solved?
How is "All strings {0,1} of length five or more in which the third symbol from the right end is different from the leftmost symbol" solved? Answer Follow·1 Request ...
paressep28
paressep28
asked
Apr 25
Theory of Computation
theory-of-computation
regular-expression
minimal-state-automata
finite-automata
pushdown-automata
+
–
85
views
0
answers
0
votes
Finite Automata Combined with Relation
Let DFA , M = (Q, ∑, δ, q$_0$, F) and Relation R is defined on Q as R:Q$\rightarrow$Q such that pRq iff $\forall$ w ∈ $\Sigma$* [ δ*(p,w) ∈ F $\leftrightarrow$ δ*(q,w) ∈ F OR δ* (p, w) ∉ F $\leftrightarrow$ δ* (q, w) ∉ F] then ____________ A) R is Reflexive B) R is Symmetric C) R is transitive D) None
Let DFA , M = (Q, ∑, δ, q$_0$, F) and Relation R is defined on Q as R:Q$\rightarrow$Q such that pRq iff $\forall$ w ∈ $\Sigma$* [ δ*(p,w) ∈ F $\leftrightarrow$ δ...
jaydip74
jaydip74
asked
Apr 23
Set Theory & Algebra
finite-automata
relations
+
–
108
views
0
answers
0
votes
Context Free language sample question
Give a context-free grammar for each of the following languages. Consider, Σ={0,1}. A. The language of strings that start with 1 B. The language of strings of the form WWR C. The language of strings that contain the substring 001 D. The language {0n10n where n ≥ 0} E. ... i, j ≥ 0} J. The language {1i01j | j is a multiple of four or i = 3 + 2j where i, j ≥ 0}
Give a context-free grammar for each of the following languages. Consider, Σ={0,1}.A. The language of strings that start with 1B. The language of strings of the form WWR...
dazeeee
dazeeee
asked
Apr 3
Theory of Computation
theory-of-computation
finite-automata
context-free-language
+
–
106
views
0
answers
0
votes
#toc
Çșȇ ʛấẗẻ
Çșȇ ʛấẗẻ
asked
Feb 24
Theory of Computation
theory-of-computation
finite-automata
regular-expression
regular-language
context-free-language
+
–
242
views
2
answers
0
votes
#Convert the NFA in to equivalent R.E.
Çșȇ ʛấẗẻ
Çșȇ ʛấẗẻ
asked
Feb 24
Theory of Computation
theory-of-computation
finite-automata
+
–
71
views
0
answers
0
votes
#TOC
Çșȇ ʛấẗẻ
Çșȇ ʛấẗẻ
asked
Feb 24
Databases
theory-of-computation
finite-automata
regular-expression
regular-language
+
–
3.1k
views
2
answers
4
votes
GATE CSE 2024 | Set 2 | Question: 12
Which one of the following regular expressions is equivalent to the language accepted by the $\text{DFA}$ given below? $0^{*} 1\left(0+10^{*} 1\right)^{*}$ $0^{*}\left(10^{*} 11\right)^{*} 0^{*}$ $0^{*} 1\left(010^{*} 1\right)^{*} 0^{*}$ $0\left(1+0^{*} 10^{*} 1\right)^{*} 0^{*}$
Which one of the following regular expressions is equivalent to the language accepted by the $\text{DFA}$ given below?$0^{*} 1\left(0+10^{*} 1\right)^{*}$$0^{...
Arjun
Arjun
asked
Feb 16
Theory of Computation
gatecse2024-set2
theory-of-computation
finite-automata
+
–
2.8k
views
2
answers
2
votes
GATE CSE 2024 | Set 2 | Question: 31
Let $\text{M}$ be the $5$-state $\text{NFA}$ with $\epsilon$-transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted by $\text{M}$? $(00)^{*}+1(11)^{*}$ $0^{*}+\left(1+0(00)^{*}\right)(11)^{*}$ $(00)^{*}+\left(1+(00)^{*}\right)(11)^{*}$ $0^{+}+1(11)^{*}+0(11)^{*}$
Let $\text{M}$ be the $5$-state $\text{NFA}$ with $\epsilon$-transitions shown in the diagram below.Which one of the following regular expressions represents the la...
Arjun
Arjun
asked
Feb 16
Theory of Computation
gatecse2024-set2
theory-of-computation
finite-automata
+
–
2.9k
views
1
answers
1
votes
GATE CSE 2024 | Set 1 | Question: 40
Consider the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\prime} s$ in $w$ and $n_1(w)$ be the number of 1 's in $w$. ... $4$ are distinguishable in $M$ States $2$ and $5$ are distinguishable in $M$ Any string $w$ with $n_0(w)=n_1(w)$ is in $L(M)$
Consider the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\...
Arjun
Arjun
asked
Feb 16
Theory of Computation
gatecse2024-set1
multiple-selects
theory-of-computation
finite-automata
+
–
261
views
0
answers
0
votes
Regular expression to finite automata
Çșȇ ʛấẗẻ
Çșȇ ʛấẗẻ
asked
Feb 15
Mathematical Logic
finite-automata
theory-of-computation
regular-expression
+
–
192
views
0
answers
0
votes
DFA construction
Each of the following languages is the complement of a simpler language. In each part, construct a DFA for the simpler language, then use it to give the state diagram of a DFA for the language given. In all parts, Σ = {a, b}. 1- {w| w does not contain the substring ab} 2- {w| ... neither the substrings ab nor ba} 4- {w| w is any string not in $a^{*}\cup b^{*}$ } ( ∪ is the union )
Each of the following languages is the complement of a simpler language.In each part, construct a DFA for the simpler language, then use it to give the state diagram of a...
rania
rania
asked
Feb 14
Theory of Computation
theory-of-computation
finite-automata
+
–
223
views
1
answers
0
votes
State diagram
Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}. 1- {w| w starts with 0 and has odd length, or starts with 1 and has even length}
Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.1- {w| w starts with 0 and has odd length, or starts with 1 and has e...
rania
rania
asked
Feb 14
Theory of Computation
theory-of-computation
finite-automata
+
–
533
views
1
answers
3
votes
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 32
Which of the following sets has the greatest cardinality? The set of real numbers R The set of all functions from R to {0,1} The set of all finite subsets of natural numbers The set of all finite-length binary strings
Which of the following sets has the greatest cardinality?The set of real numbers RThe set of all functions from R to {0,1}The set of all finite subsets of natural numbers...
GO Classes
GO Classes
asked
Feb 5
Theory of Computation
goclasses2024-mockgate-14
theory-of-computation
finite-automata
1-mark
+
–
613
views
1
answers
6
votes
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 24
Let $\mathrm{M}$ be a $8$-state Deterministic Finite Automaton over the alphabet $\{a, b, c\}$. If the language accepted by $\text{M}$ i.e. $\text{L(M)}$ is finite, then the maximum possible cardinality of $\text{L(M)}$ is __________.
Let $\mathrm{M}$ be a $8$-state Deterministic Finite Automaton over the alphabet $\{a, b, c\}$. If the language accepted by $\text{M}$ i.e. $\text{L(M)}$ is finite, then ...
GO Classes
GO Classes
asked
Jan 28
Theory of Computation
goclasses2024-mockgate-13
goclasses
numerical-answers
theory-of-computation
finite-automata
1-mark
+
–
419
views
1
answers
4
votes
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 25
A garage door opens if it ever sees the password $011$ in a transmission. More formally, this FSM takes a bitstring consisting of $\text{0's}$ and $\text{1's}$ as its input, and continually outputs $\text{0's}$ until it sees the substring $011,$ ... Arrow $1 - (0/0)$ Arrow $3 - (1/0)$ Arrow $4 - (1/0)$ Arrow $5 - (1/1)$
A garage door opens if it ever sees the password $011$ in a transmission. More formally, this FSM takes a bitstring consisting of $\text{0's}$ and $\text{1's}$ as its inp...
GO Classes
GO Classes
asked
Jan 28
Digital Logic
goclasses2024-mockgate-13
goclasses
digital-logic
sequential-circuit
finite-automata
multiple-selects
1-mark
+
–
520
views
1
answers
3
votes
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 15
Consider the following NFA $M$ and say what language is recognised by constructing the machine that recognises the complement of $L(M)$ in $\{a\}^*$. $\emptyset$ $\{a\}^*$ $\{a\}$ $\{\varepsilon\}$
Consider the following NFA $M$ and say what language is recognised by constructing the machine that recognises the complement of $L(M)$ in $\{a\}^*$.$\emptyset$$\{a\}^*$$...
GO Classes
GO Classes
asked
Jan 21
Theory of Computation
goclasses2024-mockgate-12
goclasses
theory-of-computation
finite-automata
1-mark
easy
+
–
741
views
1
answers
8
votes
GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 43
Let $\text{D}$ be a DFA with $n$ states $\& \;\text{N}$ be an NFA with $n$ states. Which of the following is/are true? If $\text{D}$ accepts some string of length $n$, then the language of $\text{D}$ is infinite ... $\mathrm{N}$ accepts some string of length $n-1$, then the language of $\mathrm{N}$ is infinite.
Let $\text{D}$ be a DFA with $n$ states $\& \;\text{N}$ be an NFA with $n$ states. Which of the following is/are true?If $\text{D}$ accepts some string of length $n$, the...
GO Classes
GO Classes
asked
Jan 21
Theory of Computation
goclasses2024-mockgate-12
goclasses
theory-of-computation
finite-automata
multiple-selects
2-marks
+
–
414
views
3
answers
4
votes
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 62
Below you see the transition table of a finite state automaton. The initial state is $0;$ the final state is $4.$ $\emptyset$ denotes the fail state, where no successful transition is possible for the given symbol. Note that when encountering a $b$ in state ... $\mathrm{abbb}^+\mathrm{c}^+\mathrm{c}$ $a b^* b b(c c)^+$
Below you see the transition table of a finite state automaton. The initial state is $0;$ the final state is $4.$ $\emptyset$ denotes the fail state, where no successful ...
GO Classes
GO Classes
asked
Jan 13
Theory of Computation
goclasses2024-mockgate-11
goclasses
theory-of-computation
finite-automata
regular-expression
2-marks
+
–
662
views
1
answers
4
votes
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 63
This question concerns two languages over the alphabet $\Sigma=\{1,-1\}$ (note that this is an alphabet with just two symbols: $1$ and $-1 ).$ The two symbols are interpreted, in the natural way, as the numbers $1$ and $-1,$ in ... $\text{L}_1$ Only $\text{L}_2$ Both None
This question concerns two languages over the alphabet $\Sigma=\{1,-1\}$ (note that this is an alphabet with just two symbols: $1$ and $-1 ).$ The two symbols are interpr...
GO Classes
GO Classes
asked
Jan 13
Theory of Computation
goclasses2024-mockgate-11
goclasses
theory-of-computation
finite-automata
regular-language
2-marks
+
–
386
views
1
answers
0
votes
Find the number of final states in DFA that recognizes L, where L= {w1a w2:|w1|≥3,|w2|≤5}, ∑={a, b} and w1, w2 ∈ ∑ * ______
Hritik1204
Hritik1204
asked
Jan 5
Theory of Computation
theory-of-computation
finite-automata
number-of-dfa
minimal-state-automata
+
–
249
views
1
answers
0
votes
Not Regular language [find out]
Why is C is regular as it non regular as? Please help me with this confusion
Why is C is regular as it non regular as?Please help me with this confusion
Deepak9000
Deepak9000
asked
Nov 27, 2023
Theory of Computation
finite-automata
theory-of-computation
regular-language
+
–
217
views
1
answers
0
votes
Regular grammar
Çșȇ ʛấẗẻ
Çșȇ ʛấẗẻ
asked
Nov 22, 2023
Theory of Computation
theory-of-computation
regular-grammar
finite-automata
+
–
359
views
1
answers
0
votes
#Regular Languages
For a particular input, a turing machine can ‘hang’ on encountering an infinite loop. Why can’t we say the same for any other machine? i.e A DFA or NFA that follows say a*(b). Will the automaton not ‘hang’ if a string $a^n$ where $n \to$ ∞ is fed to it? Isn’t ‘never accepting but progressing’ the same as hanging?
For a particular input, a turing machine can ‘hang’ on encountering an infinite loop. Why can’t we say the same for any other machine? i.e A DFA or NFA that follows...
Mrityudoot
Mrityudoot
asked
Oct 21, 2023
Theory of Computation
theory-of-computation
regular-expression
finite-automata
regular-language
+
–
243
views
1
answers
0
votes
Automata and Formal Languages
jam
jam
asked
Oct 17, 2023
Theory of Computation
theory-of-computation
finite-automata
+
–
281
views
1
answers
0
votes
Please help how to draw dfa
Çșȇ ʛấẗẻ
Çșȇ ʛấẗẻ
asked
Oct 2, 2023
Theory of Computation
finite-automata
+
–
Page:
1
2
3
4
5
6
...
35
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register