Consider the regular expression: (albic)*a(albic) (albic)...(albic) which has on the right the term (alb|c) n-1 times,...

 

Transcribed Image Text:

Consider the regular expression: (albic)*a(albic) (albic)...(albic) which has on the right the term "(alb|c)" n-1 times, and describes in the alphabet {'a', 'b', 'c'} the language of strings in which the nth symbol from the end is 'a'. For example, if n = 4, the strings "bbcacba", "abba" belong to the language, while the "babc", "cbca" do not belong to it. A. For each value of n, how many states at least should any deterministic finite automaton have does it recognize regular expression strings and why? B. How does your answer change if the nth term from the end becomes "(alb)" instead of "a" and why? C. How do your answers change if o is added to the end of the regular expressions in both cases term "(alb|c)*" and why? Consider the regular expression: (albic)*a(albic) (albic)...(albic) which has on the right the term "(alb|c)" n-1 times, and describes in the alphabet {'a', 'b', 'c'} the language of strings in which the nth symbol from the end is 'a'. For example, if n = 4, the strings "bbcacba", "abba" belong to the language, while the "babc", "cbca" do not belong to it. A. For each value of n, how many states at least should any deterministic finite automaton have does it recognize regular expression strings and why? B. How does your answer change if the nth term from the end becomes "(alb)" instead of "a" and why? C. How do your answers change if o is added to the end of the regular expressions in both cases term "(alb|c)*" and why?

Answer rating: 100% (QA)

A For each value of n a deterministic finite automaton DFA should have at least n1 states to recogni... View the full answer