Which of the following are correct? (There may be more than one correct answer)

Question

Which of the following are correct? (There may be more than one correct answer)

A. A CFL for the set 0^n1^n is: S->0S1 | . Note that here 0^n1^n is the set of all strings of zero, or one, or more 0’s followed by an equal number of 1’s.

B.

A CFL for the language {a^i b^j c^k} such that either i is not equal to j or j is not equal to k with the alphabet of {a, b, c} is:

S -> S1 c | a S2

S1 -> T1 | T2

T1-> a T1 | a T1 b |

T2-> T2b | a T2 b |

S2-> T3|T4

T3-> b T3 | b T3 c |

T4-> T4 c | b T4 c |

C.

A CFL for the set of strings over 0 and 1 with odd length is:

S-> 00S|01S|10S|11S|1|0

D. The following DFA recognize the language of all positive integer numbers

Explanation / Answer

A is correct.

S->0S1

S->00S11

.

.

.

S->0n1n

Applying

S-> S->0n1n

C is correct

S->0

S->1

Generates string of length 1 which is odd.

S->00S

->0000S

Replacing S by either 0 or 1 generates a string of odd length.

D is correct

From the starting state if we get any decimal digits we move to the final state.If we receive + sign we move o the next state and on receiving decimal digits we mov to final state.If we receive – or 0 we move to dead state.

B is not correct

Because from the variable T1 and T2 we may get a string where i is equal to j or j is equal to k

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.