Question

Design a finite automata which has neither aa nor bb as substring

Answer 1

Explanation:

A regular language is a language that can be expressed with a regular expression or a deterministic or non-deterministic finite automata or state machine. ... Regular languages are used in parsing and designing programming languages and are one of the first concepts taught in computability courses.

Answer 2

We can design a finite automata that recognizes strings that do not have "aa" or "bb" as a substring by following these steps:

• Start with an initial state, q0.

• Create two states for each possible prefix of "aa" and "bb" respectively. For example, create states q1 and q2 for the prefix "a" and create states q3 and q4 for the prefix "b".

• Create a separate state for each possible suffix of "aa" and "bb" respectively. For example, create states q5 and q6 for the suffix "a" and create states q7 and q8 for the suffix "b".

• For each state that corresponds to a valid prefix or suffix, create transitions to the appropriate state for the next character in the string. For example, from q1, create a transition to q0 for any character other than "a". From q5, create a transition to q6 for "a" and back to q0 for any other character.

• Create transitions from the initial state q0 to the appropriate prefix states depending on the first character of the input string. For example, from q0, create a transition to q1 for "a" and q3 for "b".

• Create transitions from each suffix state to the final accepting state, qf.

• Create a non-accepting dead state, qd, and add transitions to it for any input that would result in a substring "aa" or "bb".

The resulting finite automata would have the following states and transitions:

q0 --a--> q1

--b--> q3

--c--> q0

--d--> q0

...

q1 --a--> qd

--b--> q2

--c--> q0

--d--> q0

...

q2 --a--> qf

--b--> qd

--c--> q0

--d--> q0

...

q3 --a--> qd

--b--> q4

--c--> q0

--d--> q0

...

q4 --a--> qd

--b--> qf

--c--> q0

--d--> q0

...

q5 --a--> q6

--b--> qd

--c--> q0

--d--> q0

...

q6 --a--> qf

--b--> qd

--c--> q0

--d--> q0

...

q7 --a--> qd

--b--> q8

--c--> q0

--d--> q0

...

q8 --a--> qd

--b--> qf

--c--> q0

--d--> q0

...

qf (accepting state)

qd (dead state)

In this automata, any input string that would contain "aa" or "bb" as a substring would transition to the dead state qd, which is a non-accepting state.

Otherwise, the automata would transition between various states until it either reaches an accepting state qf (which represents a string that does not contain "aa" or "bb" as a substring) or the dead state qd.

To know more :-

https://brainly.in/question/1364529?referrer=searchResults

https://brainly.in/question/51819912?referrer=searchResults

#SPJ6