Рубрики

Теория автоматов | Набор 3

На экзамене GATE CS 2011 были заданы следующие вопросы.

1) Лексический анализ для современного языка, такого как Java, нуждается в мощности какой-либо из следующих моделей машин в необходимом и достаточном смысле?
(A) Конечные автоматы
(B) Детерминированные автоматы нажатия
(C) Недетерминированные автоматы нажатия
(D) машина Тьюринга

Ответ (А)
Лексический анализ — это первый шаг в компиляции. В лексическом анализе программа делится на токены. Лексические анализаторы обычно основаны на автоматах конечного состояния. Токены обычно могут быть выражены в виде различных регулярных выражений:
Идентификатор задается как [a-zA-Z] [a-zA-Z0-9] *
Ключевое слово if задается if.
Целые числа задаются как [+ -]? [0-9] +.

2) Какие из следующих пар обладают РАЗЛИЧНОЙ выразительной силой?
(A) Детерминированные конечные автоматы (DFA) и Недетерминированные конечные автоматы (NFA)
(B) Детерминированные автоматы нажатия (DPDA) и Недетерминированные автоматы нажатия
(C) Детерминированная одноленточная машина Тьюринга и Недетерминированная одноленточная машина Тьюринга
(D) Одноленточная машина Тьюринга и многоленточная машина Тьюринга

Ответ (Б)
DPDA не может обрабатывать языки или грамматики с неоднозначностью, но NDPDA может обрабатывать языки с неоднозначностью и любой контекстно-свободной грамматикой.

3) Детерминированная конечная автоматизация (DFA) D с алфавитом ∑ = {a, b} приведена ниже

Какой из следующих конечных автоматов является допустимым минимальным DFA, который принимает тот же язык, что и D?

Ответ (А)
Опции (B) и (C) недопустимы, потому что они оба принимают 'b' в виде строки, которая не принимается, дают DFA. D недействителен, потому что он принимает bb + a, которые не принимаются данным DFA.

Пожалуйста, смотрите GATE Corner для всех документов / решений / объяснений предыдущего года, учебных планов, важных дат, заметок и т. Д.

Пожалуйста, пишите комментарии, если вы найдете какие-либо неправильные ответы / объяснения, или вы хотите поделиться дополнительной информацией по темам, обсужденным выше.

Рекомендуемые посты:

Теория автоматов | Набор 3

0.00 (0%) 0 votes