Provide state diagram of dfas recognizing the languages

Assignment Help Theory of Computation

Reference no: EM13693765

Question 1: Provide state diagram of DFAs recognizing the subsequent languages (the alphabet is {0,1}):

a) L1 = the set of all strings that start with 0 and have odd length

b) L2 = the set of all strings that start with 1 and have even length

c) L3 = the set of all strings that end with 1 and have even number of 1s

d) L1 U L2

e) L1 U L3

f) The set of all strings such that every occurrence of 0 is followed by at least two 1s, e.g.,

0111, 01101111011111, 1110111 are in this language, but 0101 is not.

g) The set of all strings that does not contain substring 101.

Question 2: Give nondeterministic finite automata accepting 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 3. (Note: 0 is an allowable multiple of 3). Try to take advantage of non determinism as much as possible.

I'm not sure how to solve these questions. Can anyone help me?

Reference no: EM13693765

Questions Cloud

How many ml of hcl solution are needed to neutralize : Problem- 10 mL of 0.50 M NH3 is titrated with 0.20 M HCl solution. How many mL of HCl solution are needed to neutralize the solution

Define amount of hcl to change the ph by one unit : Problem- With three buffers with three different pH's (5,6, and 4), why is it that each buffer would need a different amount of NaOH to change the pH by one unit? Why is it that each buffer would require a different amount of HCL to change the pH ..

Define the operations using peano arithmetic : Write five tests for each using numbers larger than 100 and verify using natZint and intZnat that your numbers work the same way as the usual natural numbers.

What is the relationship if any between solution color : What is the relationship if any between solution color and visible light interaction. can solution color be predicted from Abs max or Trans max colors. give examples.

Provide state diagram of dfas recognizing the languages : Give nondeterministic finite automata accepting 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 3.

The centrifuge tube after acetone extraction fizzes : Problem- The white solidt hat remains in the centrifuge tube after acetone extraction fizzes when hydrochloric acid is added, suggesting the sodium carbonate is present. How did this substance form

64-bit architecture : How would you design software to do this (Use a maximum of one to two paragraphs of 5-7 sentences each)?

Number of permutation of elements of a : Prove that the number of subsets of elements in A is less than the number of permutation of elements of A

Two numbers in 8 bit twos complement : Two numbers in 8 bit two's complement do not have inverses? That is, they cannot be negated by taking the two's complement.

User Account

All Pages