• 検索結果がありません。

解析表現文法の決定性有限オートマトン化判定

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "解析表現文法の決定性有限オートマトン化判定"

Copied!
1
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 1 ページ )

全文

(1)情報処理学会論文誌. プログラミング. Vol.9 No.2 3 (May 2016). 発表概要. 解析表現文法の決定性有限オートマトン化判定 千田 忠賢1,a). 佐藤 正典1. 倉光 君郎1. 2015年11月5日発表. 正規表現は，解析表現と決定性有限オートマトン（DFA）に変換できることが知られている．解析表現 文法は再帰を表現できるため，すべての解析表現を DFA に変換することはできない．しかし，正規表現か ら変換された解析表現文法から DFA への変換アルゴリズムの存在は予想される．このことから，DFA に 変換できる特定の解析表現の存在が予想される．本稿では，解析表現文法特有の記法である優先度付き選 択や非終端記号のうち DFA 化できるクラスの範囲について論じ，DFA に変換できる解析表現を明確にす る．また，任意の解析表現文法に対する DFA 化判定アルゴリズムについて説明する．. Judgement of Converting Parsing Expression Grammar into Deterministic Finite Automaton Nariyoshi Chida1,a). Masanori Sato1. Kimio Kuramitsu1. Presented: November 5, 2015. It is well-known that regular expressions can be converted into Parsing Expression Grammars (PEGs) and Deterministic Finite Automata (DFA). It is impossible that converting all PEGs into DFA. For example, PEGs can represent recursion. But we can expect existence of an algorithm that converts PEGs derived by regular Expression into DFA. For the reason, we can expect the existence of a PEGs class that in convertible into DFA. In this paper, we discuss about the class that contains Prioritized choice and Non Terminal and convertible into DFA. In addition, we clarify the PEG class that is convertible into DFA. Finally, we propose an algorithm that judge whether the PEG is convertible into DFA.. 1. a). 横浜国立大学 Yokohama National University, Yokohama, Kanagawa 240– 8501, Japan [email protected]. c 2016 Information Processing Society of Japan . 3.

(2)

参照

今ダウンロードする ( PDF - 1 ページ - 76.78 KB )

関連したドキュメント

An inductive approach to Coxeter arrangements and Solomon’s descent algebra

arXiv:1101.2075 (2011)), we claimed that both the group algebra of a finite Coxeter group W as well as the Orlik–Solomon algebra of W can be decomposed into a sum of

It is assumed that the restoring force is asymptotically negligible as the solution becomes large, and that the per- turbation tends to zero as time becomes indefinitely large

We have formulated and discussed our main results for scalar equations where the solutions remain of a single sign. This restriction has enabled us to achieve sharp results on

4 Some solutions of the Sturm–Liouville hierarchy

It is also well-known that one can determine soliton solutions and algebro-geometric solutions for various other nonlinear evolution equations and corresponding hierarchies, e.g.,

If

We give another global upper bound for Jensen’s discrete inequal- ity which is better than already existing ones.. For instance, we determine a new converses for generalized A–G and

Locally realcompact and HN-complete spaces

It is known that a space is locally realcompact if and only if it is open in its Hewitt-Nachbin realcompactification; we give an external characterization of HN- completeness

It is proven that at least a critical point of the transformed functional is obtained, which directly translates to the original functional

7.1. Deconvolution in sequence spaces. Subsequently, we present some numerical results on the reconstruction of a function from convolution data. The example is taken from [38],

PROFINITE TOPOLOGICAL SPACES

A topological space is profinite if it is (homeomorphic to) the inverse limit of an inverse system of finite topological spaces. It is well known [Hoc69, Joy71] that profinite T 0

It is also provided an example showing that L1-weak ergodicity is weaker that weak ergodicity

In this paper we study certain properties of Dobrushin’s ergod- icity coefficient for stochastic operators defined on noncommutative L 1 -spaces associated with semi-finite von