Конечный автомат в схеме

Question

Я пытаюсь закончить конечный автомат в Схеме.Проблема в том, что я не уверен, как сказать ему, какие символы он должен тестировать.Если я хочу проверить строку "abc112", то как мне это сделать?

Вот код:

#lang racket    
(define (chartest ch)
  (lambda (x) (char=? x ch)))
;; A transition is (list state char!boolean state)
(define fsmtrlst 
  (list
   (list 'start char-alphabetic? 'name)
   (list 'start char-numeric? 'number)
   (list 'start (chartest #\() 'lparen)
   (list 'start (chartest #\)) 'rparen)
   (list 'name char-alphabetic? 'name)
   (list 'name char-numeric? 'name)
   (list 'number char-numeric? 'number)))

(define (find-next-state state ch trl)
  (cond
    [(empty? trl) false]
    [(and (symbol=? state (first (first trl)))
          ((second (first trl)) ch))
     (third (first trl))]
    [else (find-next-state state ch (rest trl))]))

(define fsmfinal '(name number lparen rparen))

(define (run-fsm start trl final input)
  (cond
    [(empty? input)
     (cond
       [(member start final) true]
       [else false])]
    [else
     (local ((define next (find-next-state start (first input) trl)))
       (cond
         [(boolean? next) false]
         [else (run-fsm next trl final (rest input))]))]))

А вот код запуска, который я пытаюсь проверить:

(fsmtrlst (list 'start (lambda (abc112) (char=? abc112 ))))

РЕДАКТИРОВАТЬ:

хорошо, .. весь продукт в порядке, но мой преподаватель не доволен этим, .. он хочет, чтобы я сделал конечный автомат с функцией перехода-> что-то вроде глобального определения, которое гласило бы: когда в состоянии X появляется символ Y, переходите к Z ... и затем я проверю список символов, чтобы увидеть, является ли он ложным или истинным ... Так что единственное отличие состоит в том, чтокод не должен быть конкретным, чтобы использовать только цифры и буквы, но любой символ ... это как-то возможно?спасибо за ваш ответ

РЕДАКТИРОВАТЬ 2: теперь у меня есть основная информация, как это должно выглядеть:

То есть машина выглядит как

A ---------> B ----------> C ----------> D ----------> (E) буква цифра цифра буква

(define fsmtrlst
 (list
   (list 'A char-alphabetic? 'B)
   (list 'B char-numeric? 'C)
   (list 'C char-numeric? 'D)
   (list 'D char-alphabetic 'E)))

(define fsmfinal '(E))

(define fsmstart 'A)

но я не уверен, как написать определение fsmstart.

Спасибо за ответы.

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

РЕДАКТИРОВАТЬ 3: Я использую онлайн-учебники и книги, которые предоставил мой учитель-наставник.Я понял, что я хотел сделать.Спасибо за вашу помощь.

Просто из любопытства:

Чем отличается довольно специфический fsm?

Пример:

START ---- "b" -----> СОСТОЯНИЕ A ----- "a" ----> СОСТОЯНИЕ B ----- "c" -----> КОНЕЧНОЕ СОСТОЯНИЕ

Тоfsm будет истинным только тогда, когда список символов «bac» и ничего больше.Возможно ли это?

Спасибо за ваш отзыв.

РЕДАКТИРОВАТЬ 4:

Хорошо, мне удалось написать, но еще раз, я не уверен, как сделатьввод символов.Это код:

Существует 3 состояния, но это будет верно только при переходе из состояния A в состояние C.

    (define (chartest ch)
    (lambda (x) (char=? x ch)))

    (define fsm-trans
       '((A, "a", B), (A, "b", A), (B, "c", C)))

    (define (find-next-state state ch trl)
      (cond
        [(empty? trl) false] 
        [(and (symbol=? state (first (first trl)))
              ((second (first trl)) ch)) <- And also this line returns an error
         (third (first trl))]
        [else (find-next-state state ch (rest trl))]))


    (define fsm-final '(C))

    (define start-state 'A)

    (define (run-fsm start trl final input)
      (cond
        [(empty? input)
         (cond
           [(member start final) true]
           [else false])]
        [else 
         (local ((define next (find-next-state start (first input) trl)))
           (cond
             [(boolean? next) false]
             [else (run-fsm next trl final (rest input))]))]))


    (run-fsm start-state fsm-trans fsm-final (list '("a", "c")))  <- I know this is the last problem with the code, the definition of the input. How can I tell Scheme what characters I want to test?

Спасибо за ваш ответ !!!

Answer 1

Мне любопытно: я так понимаю, вы не написали этот fsm? Это для домашнего задания или вы пытаетесь научить себя? Код для FSM выглядит хорошо (на самом деле вполне нормально). Тем не менее, ваша линия запуска:

(fsmtrlst (list 'start (lambda (abc112) (char=? abc112 ))))

Не имеет смысла. Вот почему: fsmtrlst - это список переходов с конечным автоматом. Это было определено в первом большом блоке кода. Это не вызываемая функция. Я считаю, что функция, которую вы хотите вызвать - run-fsm. Для этого требуется начальный символ, список переходов, список конечных состояний и входные данные. На самом деле ввод - это не строка, а список. Как следствие, вы можете запустить его со следующей строкой:

(run-fsm 'start fsmtrlst fsmfinal (string->list "abc112"))

Это вызовет run-fsm с определенным списком переходов fsmtrlst, определенным списком конечных состояний и готовой к вводу строкой "abc112".

Кстати, все, кроме 'start, определено как конечное (принимающее) состояние. Однако не все входные данные принимают входные данные. Например, замена "abc122" на "abc (122" не принята.

Это то, что вы хотите?

Обновление:

Ваша редакция прояснила ситуацию. Ваше определение fsmstart в порядке. Вы пропустили вопросительный знак (?) На одном из ваших char-alphabetic? употреблений в fsmtrlst. Есть ли у вас путаница, что вы не знаете, как использовать ваши новые определения? Во-первых, вы должны удалить старые определения fsmtrlst и fsmfinal. В противном случае вы, вероятно, получите ошибку определения дубликата. Из вашего нового определения ваша строка для выполнения должна выглядеть следующим образом:

(run-fsm fsmstart fsmtrlst fsmfinal (string->list "w00t"))

Это вернет #t, потому что «w00t» - это символ, за которым следуют два числа, за которыми следует символ.

Я предполагаю, что у вас все еще возникают проблемы с правилами синтаксиса схемы, а не только с логикой вашей конкретной программы. Возможно, вы захотите попробовать более простое упражнение.

ОБНОВЛЕНИЕ 2: не должны ли вы подумать о формулировании нового вопроса?

Ваше последнее обновление нарушило код. Переходная часть fsm работала, потому что переходы были определены как список:

(from-state test-function to-state)

Вы попытались создать переход:

(from-state string-literal to-state)

Вы можете изменить (A, "a", B) на (A (lambda (x) (string=? x "a") B).

Когда вы пытались вызвать вашу функцию, вы взяли функцию, которая ожидала список символов, и дали ей список списка строк. Это не одно и то же. Кроме того, вы заметили, что вы помещаете запятые в свои списки, но они не существуют нигде в коде? Именно из-за этих ошибок я предлагаю вам начать учебник по схеме. Это основные проблемы схемы, не связанные с вашим конкретным упражнением. Я предлагаю вам перемотать свои правки к тому, что было вчера.

К сожалению, я больше не могу обновить этот ответ. Я хотел бы обновить свой ответ, чтобы, если кто-то придет на ваш вопрос с аналогичными проблемами, он увидел полный ответ. Однако вы указали движущуюся цель. Пожалуйста, подумайте о том, чтобы прервать редактирование и отправить новый вопрос, если он у вас есть.