System for determining whether or not automaton satisfies context-free grammar

摘要

A server that holds context-free grammar and is connectable to a client that holds an automaton. The server compares an edge pair with an encrypted string value such that the encrypted string value is hidden from the client. The edge pair represents a string for an encrypted value in which a nonfinal character is made to correspond to a state before and the state after held by the client and an encrypted string value represents a string for an encrypted value in which each of a plurality of nonfinal characters contained in a substituted symbol string for a production rule for the context-free grammar is given correspondence with an assigned state before and state after. The encrypted value in which in which the encrypted string value matches the edge pair has been encrypted is sent to the client along with the state before and state after that has been assigned.