Bộ chuyển đổi trạng thái hữu hạn là gì?

Question

Ai đó có thể cho tôi biết bộ chuyển đổi trạng thái hữu hạn là gì không?

Tôi đã đọc the Wikipedia article và không hiểu gì.

Answer 1

Bộ chuyển đổi trạng thái hữu hạn (FST) là một hệ thống tự động hữu hạn (FSA, FA) tạo đầu ra cũng như đầu vào đọc, có nghĩa là rất hữu ích cho việc phân tích cú pháp (trong khi FSA "trần" chỉ có thể được sử dụng để nhận dạng) , ví dụ: khớp mẫu).

FST bao gồm số lượng hữu hạn các trạng thái được liên kết bằng các hiệu ứng chuyển tiếp được gắn nhãn với cặp đầu vào/đầu ra. FST bắt đầu ở trạng thái bắt đầu được chỉ định và nhảy đến các trạng thái khác nhau tùy thuộc vào đầu vào, trong khi tạo ra đầu ra theo bảng chuyển tiếp của nó.

FST hữu ích trong NLP và nhận dạng giọng nói vì chúng có các thuộc tính đại số tốt, đáng chú ý nhất là chúng có thể được kết hợp tự do (tạo thành một đại số) theo thành phần, thực hiện thành phần quan hệ trên quan hệ thường xuyên (nghĩ về điều này là không xác định) chức năng thành phần) trong khi ở rất nhỏ gọn. FST có thể phân tích các ngôn ngữ thông thường thành các chuỗi theo thời gian tuyến tính.

Ví dụ, tôi đã từng triển khai phân tích cú pháp hình thái như một loạt các FST. FST chính của tôi cho động từ sẽ biến một động từ thông thường, nói "đi", thành "walk + PAST". Tôi cũng đã có một FST cho động từ "được", mà sẽ biến "là" thành "được + PRESENT + 3rd" (người thứ 3), và tương tự cho các động từ bất quy tắc khác. Tất cả các FST được kết hợp thành một trình đơn duy nhất sử dụng trình biên dịch FST, nó tạo ra một FST đơn lẻ nhỏ hơn nhiều so với tổng các phần của nó và chạy rất nhanh. FST có thể được xây dựng bằng nhiều công cụ chấp nhận cú pháp biểu thức chính quy mở rộng.

Answer 2

Trình chuyển đổi trạng thái hữu hạn về cơ bản là một automaton hữu hạn của tiểu bang hoạt động trên hai (hoặc nhiều) băng. Cách phổ biến nhất để suy nghĩ về đầu dò là một loại máy dịch ''. Họ đọc từ một trong những cuốn băng và viết lên băng kia. Này, ví dụ, là một bộ chuyển đổi mà dịch a s vào b s:

a:b tại vòng cung có nghĩa là trong quá trình chuyển đổi này đầu dò đọc a từ băng đầu tiên và viết b vào thứ hai.

tham khảo: Finite State Transducers

Answer 3

Trong nhiệm kỳ làm đơn giản càng tốt, tôi hiểu rằng một FST bản chất là một "điều" mà di chuyển từ một trạng thái này sang thế dựa trên một băng đầu vào và ghi vào một đầu ra khác nhau băng. Một băng cơ bản là một tập hợp các đầu vào như các ký tự trong một chuỗi.

Toàn bộ FST được thể hiện bằng một tập hợp các trạng thái và liên kết giữa chúng. Một liên kết được "kích hoạt" khi điều kiện đầu vào của nó là chính xác và sau đó đưa ra sau đó nhà nước tiếp theo băng điều chỉnh.

Ví dụ: giả sử FST bắt đầu bằng băng abc ở trạng thái 1. Liên kết đến trạng thái 2 khớp với a và thay đổi thành b. Điều này sẽ được kích hoạt, thiết lập băng đầu ra thành chỉ b và chuyển số còn lại bc sang trạng thái 2. Như bạn thấy, mỗi trạng thái chỉ được kích hoạt nếu có liên kết đến nó có điều kiện đầu vào chính xác, chuyển đầu vào còn lại trạng thái tiếp theo và ghi vào một băng đầu ra riêng biệt. Mỗi FST chạy trên băng một lần và xuất ra một băng khác một lần.

Để hiểu rõ hơn về chúng read and take a look at the diagrams in this article.