Scribd
Upload
11 views1 page

FSM String Acceptance Tutorial Guide

The document contains instructions and examples for finite state machines (FSMs). It asks the reader to determine which strings are accepted by 5 sample FSMs and describe the strings each accepts. It then asks the reader to construct FSMs that accept specific languages, including a language containing only the string 0110, all binary strings with at least one 0, all binary strings with at most one 0, and all binary strings starting and ending with 0. It also asks the reader to construct FSMs over the alphabet {a, b, c} that accept strings with an odd number of a's, strings containing "abc" as a substring, and strings whose symbols are in alphabetical order.

Uploaded by

Darian Chetty
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views1 page

FSM String Acceptance Tutorial Guide

The document contains instructions and examples for finite state machines (FSMs). It asks the reader to determine which strings are accepted by 5 sample FSMs and describe the strings each accepts. It then asks the reader to construct FSMs that accept specific languages, including a language containing only the string 0110, all binary strings with at least one 0, all binary strings with at most one 0, and all binary strings starting and ending with 0. It also asks the reader to construct FSMs over the alphabet {a, b, c} that accept strings with an odd number of a's, strings containing "abc" as a substring, and strings whose symbols are in alphabetical order.

Uploaded by

Darian Chetty
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

COMP107 Tutorial 3 2021

1. For the FSMs given below, determine which of the strings 0110, 1, 1011010 , 00000 are accepted.

2. Describe in a sentence, the strings accepted by each of the FSM’s below.

0,1
0 1
a) A B C
0,1

1
1
b) A B
0 0

0 0 0,1

1 1
c) A B C

A B
0

d) 1 1 1 1

0
C D
0

0 0

e) 0 1
0,1
A C

1 1

3. Give FSM’s that accepts each of the following languages:


a) A language containing only the string 0110.
b) All binary strings with at least one 0
c) All binary strings with at most one 0
d) All binary strings starting and ending with 0

4. Given the alphabet {a, b, c}, construct FSM’s that accepts strings:
a) that contain an odd number of a’s.
b) that contain abc as a substring.
c) whose symbols are in alphabetical order. (For example, aaabcc and ac are okay; abca and cb are not.)

You might also like