Детерминированные автоматы-распознаватели

31. Построить конечный автомат, распознающий язык , при условии, что слово w принадлежит языку L тогда и только тогда, когда в этом слове

а) буква с встречается ровно 1 раз;

б) буква b встречается ровно два раза;

в) буква a встречается не менее двух раз.

32. Найти конечный автомат, распознающий язык

а) ; б) { a,b } * .

33. Найти конечный автомат с однобуквенными переходами, распознающий язык

а) ; б) .

34. Является ли детерминированным следующий конечный автомат? Какой язык он распознает?

Преобразуйте полученный автомат в детерминированный.

35. Построить детерминированный конечный автомат, распознающий язык , при условии, что слово w принадлежит языку L тогда и только тогда, когда

а) в этом слове буква a встречается четное число раз;

б) в нем содержится подслово abbc;

в) в этом слове буква a не встречается дважды подряд.

36. Построить детерминированный конечный автомат, распознающий язык , при условии, что слово w принадлежит языку L тогда и только тогда, когда

а) в этом слове первая буква совпадает с последней;

б) в нем содержится подслово bbaa;

в) оно содержит четное число букв.

37. Построить детерминированный конечный автомат, распознающий множество слов в алфавите A ={ а ₁, а ₂, …, а_k }, длина которых кратна n.

38. Найти детерминированный конечный автомат, распознающий язык

а) ; б) ;

в) .

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

а) ;

б) .

Являются ли построенные автоматы полными?

40. Найти полный детерминированный конечный автомат, эквивалентный автомату, изображённому на диаграмме.

41. Построить грамматики, порождающие языки, распознаваемые автоматами иззадач 35(а, б).

42. Построить грамматики, порождающие языки, распознаваемые автоматами иззадач 36(б, в).

43. Существует ли такой автоматный язык L, что язык L^R не является автоматным?

Занятие 5. Свойства автоматных языков. Регулярные выражения.