Man of Honour
- Joined
- 15 Mar 2004
- Posts
- 28,140
- Location
- Liverpool
Allo, am running through my notes on Automata theory and languages. I'm unsure of a few things, possibly because more than one answer is possible.
Q)Consider the language that consists of all words over the alphabet {a,b,c}, that either begin with the letter a, or begin with b and contain exactly three c's.
a) draw a diagram of a deterministic finite automaton that accepts the language
b) Write a regular expression for the language, and explain briefly how our regular expression corresponds with the language
I get :
States 1,2,3,4,5,6. States 1 to 2 with an arrow labelled a. States 1 to 3 with an arrow labelled b. States 3,4,5,6 loop themselves with an arrow each, labelled a,b. States 1 to 3, 3 to 4, 4 to 5 and 5 to 6 have arrows with c above them. State 5 is an accepting state.
How do I pull out a regular expression for part b) ? I understand that an RE uses U, concat and Keene*.
Similarly for this question, how do I get a regular expression please?
Q)Consider the following NFA A=(Q,A,PHI,i,T) where :
alphabet A ={a,b}
states Q={i,r,s,t}
accepting states T={s,t}
transition function PHI is :
PHI(i,a)=r PHI(r,b)=s PHI(s,a)={r,t} PHI(t,b)=t
Again, the question asks to create a regular expression.
Any help would be appreciated, preferably in prose rather than formally please.
Q)Consider the language that consists of all words over the alphabet {a,b,c}, that either begin with the letter a, or begin with b and contain exactly three c's.
a) draw a diagram of a deterministic finite automaton that accepts the language
b) Write a regular expression for the language, and explain briefly how our regular expression corresponds with the language
I get :
States 1,2,3,4,5,6. States 1 to 2 with an arrow labelled a. States 1 to 3 with an arrow labelled b. States 3,4,5,6 loop themselves with an arrow each, labelled a,b. States 1 to 3, 3 to 4, 4 to 5 and 5 to 6 have arrows with c above them. State 5 is an accepting state.
How do I pull out a regular expression for part b) ? I understand that an RE uses U, concat and Keene*.
Similarly for this question, how do I get a regular expression please?
Q)Consider the following NFA A=(Q,A,PHI,i,T) where :
alphabet A ={a,b}
states Q={i,r,s,t}
accepting states T={s,t}
transition function PHI is :
PHI(i,a)=r PHI(r,b)=s PHI(s,a)={r,t} PHI(t,b)=t
Again, the question asks to create a regular expression.
Any help would be appreciated, preferably in prose rather than formally please.
Last edited:
