Learnability of languages is a chal

Learnability of languages is a challenging problem
in the domain of formal language identi¯cation. It is
known that the e±ciency of a learning technique can
be measured by the size of some good samples (rep-
resentative or distinctive samples) formally called a
characteristic set. Our research focuses on the char-
acteristic set of k-acceptable languages. We proposed
a Gold-style learning algorithm called KRPNI which
applied the grammatical inference technique to iden-
tify a language and expressed it by a k-DFA. In this
paper, we study the existence of such characteristic
sets. Our theoretical results show that there exists a
polynomial characteristic set for a k-acceptable lan-
guage. It is found that the size of the characteristic
set depends on the value of k, instead of the size of
an alphabet.

ผลลัพธ์ (ไทย) 1:

Learnability ภาษาเป็นปัญหาท้าทาย
ในโดเมนของ identi¯cation ภาษาทางการ เป็น
เรียกว่า e±ciency เป็นเทคนิคการเรียนรู้สามารถ
วัดตามขนาดของตัวอย่างดี (ตัวแทน-
ตัวอย่าง resentative หรือโดดเด่น) เรียกว่าอย่างเป็นกิจจะลักษณะเป็น
ชุดลักษณะ วิจัยของเราเน้นอักขระ-
acteristic ชุดภาษา k ยอมรับ เราเสนอ
ขั้นตอนวิธีเรียนทองแบบที่เรียกว่า KRPNI ซึ่ง
ใช้เทคนิคข้อไวยากรณ์การ iden-
tify ภาษา และแสดง โดยเค-DFA ใน
กระดาษ เราศึกษาการดำรงอยู่ของลักษณะเช่น
ชุด แสดงผลลัพธ์ของทฤษฎีของเราที่มีอยู่การ
ลักษณะพหุนามตั้งสำหรับ k ยอมรับแลนแบบ
guage พบว่าขนาดของลักษณะ
ชุดขึ้นอยู่กับค่าของ k แทนขนาดของ
ตัวอักษร

ผลลัพธ์ (ไทย) 3:

learnability ภาษาเป็นปัญหาที่ท้าทาย
ในโดเมนของภาษาอย่างเป็นทางการ identi ¯ไอออนบวก มันเป็นที่รู้จักกันว่า e
±ประสิทธิภาพของเทคนิคการเรียนรู้สามารถ
ถูกวัดโดยขนาดของบางอย่างที่ดี ตัวอย่าง ( ตัวแทน -
resentative หรือโดดเด่นตัวอย่าง ) อย่างเป็นทางการเรียกว่า
ลักษณะชุด เราวิจัยใน char -
acteristic ชุด k-acceptable ภาษา เราเสนอ
ทองสไตล์การเรียนรู้ขั้นตอนวิธีเรียก krpni ซึ่งใช้เทคนิคการอนุมานไวยากรณ์
-
tify เอกลักษณ์ภาษาและแสดงโดย k-dfa . ในกระดาษนี้
เราศึกษาการดำรงอยู่ของลักษณะดังกล่าว
ชุด ผลทางทฤษฎีพบว่ามีอยู่ 6 ลักษณะการตั้งค่าสำหรับ k-acceptable
-
LAN , . พบว่าขนาดของลักษณะ
ขึ้นอยู่กับค่า K แทนขนาดของ
ตัวอักษร .