Register

Recent questions and answers in Theory of Computation

0 votes
0 answers
1
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}
User Avatar
1 votes
0 answers
4
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 ...
User Avatar
0 votes
2 answers
8
Regular language
Can anyone explain how we can write this regular language for the following diagram ?(in depth)
Can anyone explain how we can write this regular language for the following diagram ?(in depth)
User Avatar
0 votes
0 answers
10
Theory of Computation | design of Turing Machine
Is this the correct Turing machine for the language $0^n 1^n0^n$? assuming $ at the end and begining of the input tape
Is this the correct Turing machine for the language $0^n 1^n0^n$?assuming $ at the end and begining of the input tape
User Avatar
0 votes
1 answer
15
Regular Expression
Set of binary strings starting with 11 and ending with 00. E.g., 1100,1110100 ,1100100
Set of binary strings starting with 11 and ending with 00. E.g., 1100,1110100 ,1100100
User Avatar
0 votes
1 answer
17
Regular Expression
Write regular expression for the set of strings of 0's and 1's with at most one pair of consecutive 1's.
Write regular expression for the set of strings of 0's and 1's with at most one pair of consecutive 1's.
User Avatar
0 votes
0 answers
22
CFL and regular language
Consider a regular language R and a context free language C. Let the PDA that recognizes C be called P=(QP,∑,Γ,δP,q0P,FP), and the DFA that reconginzes R be (QR,∑,δR,q0R,FR).
Consider a regular language R and a context free language C. Let the PDA that recognizes C be called P=(QP,∑,Γ,δP,q0P,FP), and the DFA that reconginzes R be (QR...
User Avatar
0 votes
0 answers
23
Pumping Lemma
Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and explain why pumping it leads to a contradiction. {aaabnan∣n≥0} {ww∣w∈Σ∗}
Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and ...
User Avatar
0 votes
1 answer
29
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...
User Avatar
0 votes
3 answers
31
michael sipser chp 1, 3rd edition, Q 12 , dfa
let D= {w | w contains an even no. of a's and an odd no. of b's and does not contain the substring ab } give a DFA with Five states that recognizes D and a regular expression that generates D.
let D= {w | w contains an even no. of a's and an odd no. of b's and does not contain the substring ab }give a DFA with Five states that recognizes D and a regular express...
User Avatar
To see more, click for all the questions in this category.