Рубрики

Заметки в последнюю минуту — теория вычислений

Смотрите последние заметки по всем предметам здесь .

Мы обсудим важные ключевые моменты, полезные для экзаменов GATE в краткой форме. Для деталей вы можете обратиться к этому .

Конечные автоматы : используется для распознавания шаблонов ввода определенного типа. Это наиболее ограниченный тип автоматов, который может принимать только обычные языки (языки, которые могут быть выражены с помощью регулярных выражений с использованием OR (+), Concatenation (.), Kleene Closure (*) как a * b *, (a + b) и т.д.)

Детерминированная FA и недетерминированная FA: В детерминированной FA имеется только один ход из каждого состояния каждого входного символа, но в недетерминированной FA может быть ноль или более одного перехода из одного состояния для входного символа.

Замечания:

  • Язык, принятый NDFA и DFA, одинаков.
  • Мощность NDFA и DFA одинакова.
  • Количество состояний в NDFA меньше или равно нет. состояний в эквивалентном DFA.
  • Для NFA с n-состояниями в худшем случае максимально возможные состояния в DFA составляют 2 n.
  • Каждый NFA может быть преобразован в соответствующий DFA.

Тождества регулярного выражения:

Φ + R = R + Φ = R
Φ * R = R * Φ = Φ
ε * R = R * ε = R
ε* = ε
Φ* = ε
ε + RR* = R*R + ε = R*

(a+b)* = (a* + b*)* = (a* b*)* = (a* + b)* = (a + b*)* = a*(ba*)* = b*(ab*)*

Машина Мура : Машины Мура — это конечные автоматы с выходным значением, и их производительность зависит только от текущего состояния.
Мили-машина : Мили-машины также являются конечными автоматами с выходным значением, и их выход зависит от текущего состояния и текущего входного символа.

Автоматы Push Down : Автоматы Pushdown имеют дополнительную память, называемую стеком, которая дает большую мощность, чем автоматы Finite. Он используется для распознавания контекстно-свободных языков.

Детерминированный и недетерминированный КПК: В детерминированном КПК имеется только один ход из каждого состояния на каждом входном символе, но в недетерминированном КПК может быть более одного перехода из одного состояния для входного символа.

Замечания:

  • Мощность NPDA больше, чем у DPDA.
  • Невозможно преобразовать каждый NPDA в соответствующий DPDA.
  • Язык, принятый DPDA, является подмножеством языка, принятого NPDA.
  • Языки, принятые DPDA, называются DCFL (детерминированные контекстно-свободные языки), которые являются подмножеством NCFL (недетерминированных CFL), принятых NPDA.

Линейно-связанные автоматы: Линейно-связанные автоматы имеют ограниченный объем памяти, называемый лентой, который можно использовать для распознавания контекстно-зависимых языков.

  • LBA более мощный, чем автомат Push down.
  •  FA < PDA < LBA < TM 

    Машина Тьюринга : Машина Тьюринга имеет ленту бесконечного размера и используется для приема рекурсивных перечислимых языков.

  • Машина Тьюринга может двигаться в обоих направлениях. Кроме того, он не принимает ε.
  • Если строка вставлена не на языке, машина остановится в неконечном состоянии.
  • Детерминированные и недетерминированные машины Тьюринга: в детерминированной машине Тьюринга имеется только один ход из каждого состояния на каждом входном символе, но в недетерминированной машине Тьюринга может быть более одного движения из одного состояния для входного символа.

    Замечания:

    • Язык, принятый NTM, multi-tape TM и DTM, одинаков.
    • Мощность NTM, Multi-Tape TM и DTM одинакова.
    • Каждый NTM может быть преобразован в соответствующий DTM.

    Хомская классификация языков:

    Grammar TypeProduction RulesLanguage AcceptedAutomataClosed Under
    Type-3 (Regular Grammar) A→a or A→aB where A,B N(non terminal) and aT(Terminal)RegularFinite AutomataUnion, Intersection, Complementation, Concatenation, Kleene Closure
    Type-2 (Context Free Grammar)

    A→ρ where A N

    and ρ (TN)*

    Context FreePush Down AutomataUnion, Concatenation, Kleene Closure
    Type-1 (Context Sensitive Grammar) α→β where α, β (TN)* and len(α) <= len(β) and α should contain atleast 1 non terminal.Context SensitiveLinear Bound AutomataUnion, Intersection, Complementation, Concatenation, Kleene Closure
    Type-0 (Recursive Enumerable)

    α →β where α, β (TN)* and α contains atleast 1 non-terminal

    Recursive EnumerableTuring MachineUnion, Intersection, Concatenation, Kleene Closure

    Отношения между ними могут быть представлены как:

    Решимые и неразрешимые проблемы:

    Язык является разрешимым или рекурсивным, если можно построить машину Тьюринга, которая принимает строки, являющиеся частью языка, и отклоняет другие. например; Число простое или нет — разрешимая проблема.

    Язык является Semi разрешимый или Рекурсивным перечислимым если машина Тьюринга может быть построена , которая принимает строки , которые являются частью языка , и это может зациклится для строк , которые не являются частью языка.

    Проблема неразрешима, если мы не можем построить алгоритм и машину Тьюринга, которые могут дать ответ «да» или «нет». например; Является ли CFG неоднозначным или нет, неразрешимо.

    Счетность:

  • Множество всех строк любого конечного алфавита исчисляемо.
  • Каждое подмножество счетного множества является либо конечным, либо счетным.
  • Набор всех машин Тьюринга исчисляется.
  • Множество всех языков, которые не являются рекурсивными перечисляемыми, неисчислимо.
  • Рекомендуемые посты:

    Заметки в последнюю минуту — теория вычислений

    0.00 (0%) 0 votes