Минимизация детерминированных конечных автоматов

44. Найти праволинейную грамматику, порождающую язык { а, b }*\ L, если язык L порождается грамматикой.

а) ;

б) .

45. Являются ли автоматными следующие языки?

а) ; б) ;

в) ; г) ;

д) ; е) { uu ^R v | и Î{ a, b }⁺, v Î{ a, b } * }.

46. Пусть A ={ а,b,с }. При каких словах и Î{ a, b } * и v Î{ a, b } * язык является автоматным?

47. Упростите регулярное выражение

а) (а * b)* + (b*a) *; б) (a + b)*(a (a + b)* a + b (a + b)* b); в) ((ab + aab)* a *)*.

48. Найти регулярные выражения для языков, допускаемых автоматами из задачи 31(а, в).

49. Найти праволинейную грамматику для следующих языков:

а) ab*a; б) ((a + b) a)*.

50. Найти регулярное выражение для языка, порождаемого грамматикой

.

51. Найти регулярное выражение для языка , где L ₁ = (aaab+c+d) *, L ₂ = (a * ba * ba * bc+d) *, L ₃ = ((a+b)* c (a+b)* cd) *.

52. Найти минимальный полный детерминированный конечный автомат для языка

а) ; б){ ab, abb }*; в) ;

г) (a+b) * (aab+abaa+abb) (a+b) *;д) (b+c)((ab) *c+ (ba) *) *; е) .