Шпаргалка по информатике

1.  Грамматика – это порождающая система

2.  Язык, определяемый формальной грамматикой, - это множество цепочек, построенных из терминальных символов и выводимых из аксиом.

3.  Инвариантом для выводов является синтаксическое дерево вывода цепочки.

4.  Грамматика называется неоднозначной, если существует цепочка, которая имеет несколько синтаксических деревьев вывода; …которая имеет несколько канонических выводов.

5.  Алгоритмическая система – способ формального описания алгоритма.

6.  Среди формальных систем: рекурсивные функции; м. Тьюринга, норм. алг. Маркова явл.  алгоритмическими системами.

7.  T=<A,Q,q0,D,F> - М.Т. A-алфавит, Q-множество состояний, q0-нач. состояние, D-программа работы, F-конечное состояние

8.  Частично рекурсивные функции эквивалентны норм. алг. Маркова

9.  Алгоритмическая система – способ формального описания алгоритмов.

10.Функция f(x,y)=x*b+y вычислима, если b>0 и b-целое

11.Алгоритмическая проблема-проблема распознаваемости и разрешимости.

12.Метод доказательства неразрешимости алг. сист. – метод сводимости

13.Множеств разрешимо, если оно само и его дополнение перечислимы.

14.Характеристическая функция перечислимого множества F(x)=1.

15.Множества M1 и M2 – разрешимы, зн., M1 U M2 – разрешимо.

16.Проблема алгоритмически не разрешима, если для её решения не существует универсального алгоритма.

17.Частично рекурсивная функция получена с помощью операций: минимизации, базовых функций или и тех и других.

18.Язык - множество цепочек в некотором алфавите.

19.Способы задания языков: формальные грамматики, регулярные выражения, конечные автоматы, среди них порождающие - формальные грамматики, регулярные выражения.

20.<Q,A,Г,d,q0,z0,F>-магазин. Q-множество состояний автомата,A-алфавит, Г-,d-функция перехода, q0-нач. сост. Авт.,z0- нач. сост. Маг.,F-множество конечных состояний.