Помогите решить задачи по теории автоматов и формальных языков!!!

СИМВОЛЫ И СТРОКИ
Задача 1
Вводится строка, состоящая из произвольных символов. Найти количество цифр и их сумму.

Задача 2
Вводится строка, состоящая из произвольных символов. Найти количество строчных букв латиницы. Заменить все строчные буквы на заглавные и наоборот.

Задача 3.
Вводится строка, состоящая из произвольных символов. Найти количество заглавных букв латиницы. Заменить каждую букву латиницы на следующую (А на В, В на С,...,Z на А и т.д.)

Регулярные грамматики
1) Построить автомат для распознавания регулярного языка. Записать язык распознаваемый автоматом в виде регулярной грамматики. Написать программу, реализующую данный автомат.
Задача 1
А={a,b,c}. Распознать язык, состоящий из всех слов, в которых встречаются все буквы, и по крайней мере одна буква встречается два раза подряд.

2) Построить конечный автомат для распознавания регулярного языка. Записать язык распознаваемый автоматом в виде регулярной грамматики. Написать программу, реализующую данный автомат

Лемма о накачке
Доказать, что заданный язык не является регулярным.
Задача 1.
А={x,y,z} Язык состоит из всех слов, в которых ни одна из букв не входит в слово два раза подряд и количество вхождений всех букв одинаково.

Автоматное программирование
Задача 1. Ячейка Excel
Построить автомат для распознавания заданного языка. Записать язык, распознаваемый автоматом в виде регулярной грамматики, записать программу, реализующую автомат:
Имя ячейки в Excel состоит из одной или нескольких букв латиницы(столбец) и натурального числа(строка). Перед символами и перед числом может стоять знак $. Номера строк начинаются с 1.
Для заданной ячейки найти и вывести номер строки и номер столбца.

Регулярные выражения
Построить конечный автомат для распознавания заданного языка. Записать язык, распознаваемый автоматом в виде регулярного выражения. Написать программу для проверки принадлежности слова языку, с использованием регулярных выражений.
Задача 1
А={0,1,2} Распознать язык, включающий все слова, которые состоят из цифр 0, 1 или только из цифр 1,2 или из 2,3.

Минимизация конечных автоматов
По заданному регулярному выражению построить автомат для распознавания языка. Привести полученный автомат к детерминированному виду. Минимизировать полученный автомат.
Задача 1
(а*сb*)*cacb
Убедительная просьба все решения подробно объяснить.

Вложения

задачи.pdf (78.5 Кб, 98 просмотров)

0

омг О_о
слепых нет

0