Register

Ullman (TOC) Edition 3 Exercise 2.3 Question 4 (Page No. 66 - 67)

• edited by
509 views
0 votes
0 votes

Give non-deterministic finite automata to accept the following languages$.$Try to take advantage of non-determinism as much as possible$.$

  1. The set of strings over the alphabet $\{0,1,.....,9\}$ such that the final digit has appeared before$.$
  2. The set of strings over the alphabet $\{0,1,.....,9\}$ such that the final digit has not appeared before$.$
  3. The set of strings of $0's$ and $1's$ such that there are two $0's$ separated by a number of positions that is a multiple of $4.$ Note that $0's$ is an allowable multiple of $4.$
• edited by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
2
admin asked Apr 2, 2019
278 views
Ullman (TOC) Edition 3 Exercise 2.3 Question 5 (Page No. 67)
In the only-if portion of Theorem $2.12$ we omitted the proof by induction on $|w|$ that if $\delta_{D}(q_{0},w)=p$ then $\delta_{N}(q_{0},w)=\{p\}.$ Supply this proof.
In the only-if portion of Theorem $2.12$ we omitted the proof by induction on $|w|$ that if $\delta_{D}(q_{0},w)=p$ then $\delta_{N}(q_{0},w)=\{p\}.$ Supply this proof.
User Avatar
0 votes
0 votes
1 answer
3
admin asked Apr 2, 2019
2,379 views
Ullman (TOC) Edition 3 Exercise 2.3 Question 3 (Page No. 66)
Convert the following NFA to a DFA and informally describe the language it accepts.
Convert the following NFA to a DFA and informally describe the language it accepts.
User Avatar
0 votes
0 votes
1 answer
4
admin asked Apr 2, 2019
623 views
Ullman (TOC) Edition 3 Exercise 2.3 Question 2 (Page No. 66)
Convert to a DFA the following NFA$:$
Convert to a DFA the following NFA$:$
User Avatar
Link Copied!