Need help with attached. Only need solutions to the following: 

1, 12-20. 

Thank you!

1. Create the finite state automaton described below:
- The finite automaton has states: A, B, C, and D.
- The start state is B.
- The final states are A and C.
- The alphabet is Σ= {c d}
- The transitions are given by the following table:
The interior entries in the table represent the end state after the input is processed.
Input c Input d
Initial State A
Initial State B A B Initial State
C C D Initial State
D B A A C 2. Given the alphabet, Σ= {p q}, give the regular expression that defines the language
consisting of all words in which ‘p’ appears quadrupled, if a ‘p’ appears at all. Thus, every
collection of p’s will contain 0, 4, 8, 12, … p’s.
3. Given the alphabet, Σ= {p t}, give the regular expression that defines the language consisting
of all words that contain exactly three or four t’s, but not more. Thus, the word ppttpptp is
legal.
4. Given the alphabet, Σ= {j h}, give the regular expression that defines the language consisting
of all strings that do not end in a triple letter.
5. Given the alphabet, Σ= {j k}, give the regular expression that defines the language consisting
of all strings that end in a triple letter.
6. Given the alphabet, Σ= {c d}, give the regular expression that defines the language
consisting of all string that have exactly one triple letter in them. Although this question is
straight-forward, there are a lot of cases and the solution is reasonably complex. You’ll make
great progress by considering the fact that ddcdcccdcd is valid word in this language. 7. Given the alphabet, Σ= {c d}, give the regular expression that defines the language
consisting of all strings in which the letter d is never quadrupled. This means no word
contains the substring dddd.
8 Given the alphabet, Σ= {p t}, give the regular expression that defines the language
consisting of all words that do not have the substring pt.
9. Describe (in English phrases) the languages associated with the following
regular expression. Don’t literally translate the expression, e.g. “c or d repeated
followed by two c’s,…”. Please be as succinct as possible. You may not
immediately see it, but there’s a simple answer.
(c + d)*cc(Λ + ddd) 10. Describe (in English phrases) the languages associated with the following
regular expression. Don’t literally translate the expression and be as succinct as
possible. Not as simple, but the pattern is there.
(c (c + ddd)*)* 11. Describe (in English phrases) the languages associated with the following
regular expression. Don’t literally translate the expression And be as succinct as
possible. Again, there is a pattern.
(c (cc)*d(dd)*)* 12. Write out the transition tables for the FA depicted below. 13. Write out the transition table for the FA depicted below. Also, this FA excepts
only one string, what is it? For Questions 14 – 20 create deterministic FAs (a few of these require some extra
effort), but all are reasonably simple.
14. Build an FA that accepts only the words ddcc, cd, and cdd and no other strings
longer or shorter. 15. Given the alphabet, Σ= {p t}, Build a FA that accepts only those words that have
more than five letters. 16. Given the alphabet, Σ= {c d}, Build an FA that accepts only those words that
have fewer than five letters. 17. Given the alphabet, Σ= {p t}, Build an FA that accepts only those words with
exactly five letters. 18. Given the alphabet, Σ= {c d}, build an FA that accepts only those words that
begin or end with a triple letter. 19. Build an FA that accepts only those words that have an even number of
substrings cdc. (i.e. cdccdc and cdccdccdccdc are accepted, but cdc and
cdccdccdc are not excepted) 20. Write a regular expression (not a programming language RegEx) for the
following FA.

• 1493881893-CS475_Assignment_2_17SP8W1.docx

ComputerScienceExpert

(11)

Status NEW Posted 04 May 2017 07:05 AM My Price 11.00

-----------

Attachments

file 1493881895-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer