(a) Construct a minimal finite state machine that accepts the language, over…

PYQ GATE 2000

(a) Construct a minimal finite state machine that accepts the language, over {0,1}, of all strings that contain neither the substring 00 nor the substring 11.

(b) Consider the grammar

S → aSAb
S → ε
A → bA
A → ε

Where S, A are non-terminal symbols with S being the start symbol; a,b are terminal symbols and ε is the empty string. This grammar generates strings of the form aⁱbʲ for some i, j ≥ 0, where i and j satisfy some condition. What is the condition on the values of i and j?

Sign up free to check your answer

Sign up free

Explore the full course: Theory Of Computation

Loading lesson…