User Tools

Site Tools


2228--t-mat-c-y-la-gi

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

2228--t-mat-c-y-la-gi [2018/11/07 17:11] (current)
Line 1: Line 1:
 +<​HTML><​br><​div id="​mw-content-text"​ lang="​vi"​ dir="​ltr"><​div class="​mw-parser-output"><​p><​b>​Ôtômat cây</​b>​ (tiếng Anh: tree automaton) là một loại máy trạng thái.<​sup class="​noprint Inline-Template Template-Fact"​ style="​white-space:​nowrap;">​[<​i><​span title="​Tuyên bố này cần tham khảo đến các nguồn đáng tin cậy.">​cần dẫn nguồn</​span></​i>​]</​sup>​ Ôtômat cây xử lý cấu trúc cây, thay vì xâu như các máy trạng thái thường gặp.
 +</​p><​p>​Bài viết này đề cập đến ôtômat phân nhánh cây, tương đương với các ngôn ngữ chính quy của cây. Một khái niệm ôtômat cây khác có thể tìm thấy là ôtômat duyệt cây. <sup class="​noprint Inline-Template Template-Fact"​ style="​white-space:​nowrap;">​[<​i><​span title="​Tuyên bố này cần tham khảo đến các nguồn đáng tin cậy.">​cần dẫn nguồn</​span></​i>​]</​sup></​p><​p>​Tương tự ôtômat cổ điển, ôtômat cây hữu hạn có thể xác định (ÔHX)<​sup class="​noprint Inline-Template Template-Fact"​ style="​white-space:​nowrap;">​[<​i><​span title="​Tuyên bố này cần tham khảo đến các nguồn đáng tin cậy.">​cần dẫn nguồn</​span></​i>​]</​sup>​ hoặc không (ÔHK)<​sup class="​noprint Inline-Template Template-Fact"​ style="​white-space:​nowrap;">​[<​i><​span title="​Tuyên bố này cần tham khảo đến các nguồn đáng tin cậy.">​cần dẫn nguồn</​span></​i>​]</​sup>​. Theo cách xử lý cây đầu vào, ôtômat cây hữu hạn có thể thuộc vào hai loại: (a) dưới lên, (b) trên xuống. Đây là vấn đề quan trọng vì mặc dù ôtômat ÔHK trên xuống và ÔHK dưới lên tương đương về khả năng biểu diễn nhưng ÔHX trên xuống kém hơn hẳn ôtômat dưới lên tương ứng vì tính chất của cây xác định bởi ÔHX trên xuống chỉ có thể phụ thuộc vào tính chất của đường đi. ÔHX dưới lên mạnh ngang với ÔHK.
 +</p>
  
 +
 +
 +<​p>​Một bảng chữ cái xếp hạng là một cặp bảng chữ cái <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle {mathcal {F}}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mrow class="​MJX-TeXAtom-ORD"><​mrow class="​MJX-TeXAtom-ORD"><​mi class="​MJX-tex-caligraphic"​ mathvariant="​script">​F</​mi></​mrow></​mrow></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle {mathcal {F}}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​205d4b91000d9dcf1a5bbabdfa6a8395fa60b676"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.927ex;​ height:​2.176ex;"​ alt="​{displaystyle {mathcal {F}}}"/></​span>​ và hàm bậc (arity) sao cho có thể xây dựng một số hạng. Các thành tố trống (bậc bằng không) còn được gọi là <​b>​hằng</​b>​. Toán hạng được xây dựng bằng các ký hiện bậc một và hằng có thể được coi là xâu. Bậc cao hơn tạo ra cây.
 +</​p><​p>​Một <​b>​ôtômat cây hữu hạn</​b>​ trên <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle F}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​F</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle F}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​545fd099af8541605f7ee55f08225526be88ce57"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.741ex;​ height:​2.176ex;"​ alt="​{displaystyle F}"/></​span>​ được định nghĩa là:
 +<span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (Q,​F,​Q_{f},​Delta )}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​mi>​Q</​mi><​mo>,</​mo><​mi>​F</​mi><​mo>,</​mo><​msub><​mi>​Q</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​f</​mi></​mrow></​msub><​mo>,</​mo><​mi mathvariant="​normal">​Δ<​!-- &Delta; --></​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (Q,​F,​Q_{f},​Delta )}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​fe0b5d620f8160128b79ededd7ee1a1c7b78c54a"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.005ex; width:​13.401ex;​ height:​3.009ex;"​ alt="​{displaystyle (Q,​F,​Q_{f},​Delta )}"/></​span>​
 +</​p><​p>​Ở đây, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Q}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​Q</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Q}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​8752c7023b4b3286800fe3238271bbca681219ed"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.838ex;​ height:​2.509ex;"​ alt="​{displaystyle Q}"/></​span>​ là tập các trạng thái, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle F}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​F</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle F}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​545fd099af8541605f7ee55f08225526be88ce57"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.741ex;​ height:​2.176ex;"​ alt="​{displaystyle F}"/></​span>​ là một bảng chữ cái xếp hạng <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Q_{f}subseteq Q}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​Q</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​f</​mi></​mrow></​msub><​mo>​⊆<​!-- &sube; --></​mo><​mi>​Q</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Q_{f}subseteq Q}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0c9005cb56e192f0c0d2a979608cdd5384a12812"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -1.005ex; width:​7.911ex;​ height:​2.843ex;"​ alt="​{displaystyle Q_{f}subseteq Q}"/></​span>​ là một tập các trạng thái kết thúc và <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Delta }"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi mathvariant="​normal">​Δ<​!-- &Delta; --></​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Delta }</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​32769037c408874e1890f77554c65f39c523ebe2"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.936ex;​ height:​2.176ex;"​ alt="​{displaystyle Delta }"/></​span>​ là tập luật chuyển trạng thái, nghĩa là các luật viết lại một nút có các con là trạng thái thành nút trạng thái mới.
 +</​p><​p>​Không có trạng thái bắt đầu nhưng các luật chuyển cho ký hiệu hằng (nút lá) có thể được coi là các luật bắt đầu. Cây được chấp nhận nếu trạng thái ở gốc là một trạng thái chấp nhận.
 +</​p><​p>​Một ôtômat hữu hạn trên xuống trên <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle F}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​F</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle F}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​545fd099af8541605f7ee55f08225526be88ce57"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.741ex;​ height:​2.176ex;"​ alt="​{displaystyle F}"/></​span>​ được định nghĩa bởi:
 +<span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle (Q,​F,​I,​Delta )}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mo stretchy="​false">​(</​mo><​mi>​Q</​mi><​mo>,</​mo><​mi>​F</​mi><​mo>,</​mo><​mi>​I</​mi><​mo>,</​mo><​mi mathvariant="​normal">​Δ<​!-- &Delta; --></​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle (Q,​F,​I,​Delta )}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​42340569f9c021b19dad2c62a3821648b181d244"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​11.598ex;​ height:​2.843ex;"​ alt="​{displaystyle (Q,​F,​I,​Delta )}"/></​span>​
 +</​p><​p>​Có hai điểm khác biệt với ôtômat cây dưới lên: thứ nhất, <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Isubseteq Q}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​I</​mi><​mo>​⊆<​!-- &sube; --></​mo><​mi>​Q</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Isubseteq Q}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​0e834e5a69e908c029fe8803fce2639241812051"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​6.109ex;​ height:​2.509ex;"​ alt="​{displaystyle Isubseteq Q}"/></​span>,​ tập trạng thái đầu thay cho <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Q_{F}}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​msub><​mi>​Q</​mi><​mrow class="​MJX-TeXAtom-ORD"><​mi>​F</​mi></​mrow></​msub></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Q_{F}}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​8e6b647a43c373e63abe85a18f2d97579f75a654"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​3.302ex;​ height:​2.509ex;"​ alt="​{displaystyle Q_{F}}"/></​span>;​ thứ hai, các luật chuyển đi theo chiều ngược lại, nghĩa là viết lại một nút trạng thái thành nút với các nút con là trạng thái. Cây được chấp nhận nếu mọi nhánh đều được duyệt qua theo cách này.
 +</​p><​p>​Các luật viết lại khiến các ký hiệu của <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle Q}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​Q</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle Q}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​8752c7023b4b3286800fe3238271bbca681219ed"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.838ex;​ height:​2.509ex;"​ alt="​{displaystyle Q}"/></​span>​ 'di chuyển'​ dọc theo các nhánh của cây.
 +</p>
 +
 +<​h3><​span id="​T.C3.ADnh_x.C3.A1c_.C4.91.E1.BB.8Bnh"/><​span class="​mw-headline"​ id="​Tính_xác_định">​Tính xác định</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​sửa<​span class="​mw-editsection-divider">​ | </​span>​sửa mã nguồn<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​h3><​span id="​Kh.E1.BA.A3_n.C4.83ng_nh.E1.BA.ADn_d.E1.BA.A1ng"/><​span class="​mw-headline"​ id="​Khả_năng_nhận_dạng">​Khả năng nhận dạng</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​sửa<​span class="​mw-editsection-divider">​ | </​span>​sửa mã nguồn<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Với một ôtômat dưới lên, một số hạng nền <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​t</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle t}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt="​t"/></​span>​ (nghĩa là một cây) được đoán nhận nếu có một phép biến đổi bắt đầu từ t và kết thúc bởi q(t). Ngược lại, với ôtômat trên xuống, một số hạng nền <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​t</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle t}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt="​t"/></​span>​ được đoán nhận nếu có một phép biến đổi bắt đầu từ q(t) và kết thúc bằng t, với q(t) là một trạng thái bắt đầu.
 +</​p><​p>​Ngôn ngữ cây <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle L(A)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​L</​mi><​mo stretchy="​false">​(</​mo><​mi>​A</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle L(A)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​fa03f64e6707e82a5a1d3e5f40176d2692e6c938"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​5.135ex;​ height:​2.843ex;"​ alt="​{displaystyle L(A)}"/></​span>​ được đoán nhận bởi ôtômat cây <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle A}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​A</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle A}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​7daff47fa58cdfd29dc333def748ff5fa4c923e3"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.743ex;​ height:​2.176ex;"​ alt="​A"/></​span>​ là tập hợp tất cả số hạng nền được đoán nhạn bởi <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle A}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​A</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle A}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​7daff47fa58cdfd29dc333def748ff5fa4c923e3"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​1.743ex;​ height:​2.176ex;"​ alt="​A"/></​span>​. Một tập các số hạng nền có thể được đoán nhận nếu tồn tại một ôtômat cây đoán nhận nó.
 +</​p><​p>​Một thuộc tính quan trọng là <​i>​biến đổi đồng hình tuyến tính (nghĩa là bảo tồn bậc) không thay đổi tính đoán nhận được</​i>​.
 +</p>
 +<​h3><​span id="​T.C3.ADnh_.C4.91.E1.BA.A7y_.C4.91.E1.BB.A7_v.C3.A0_gi.E1.BA.A3n_l.C6.B0.E1.BB.A3c"/><​span class="​mw-headline"​ id="​Tính_đầy_đủ_và_giản_lược">​Tính đầy đủ và giản lược</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​sửa<​span class="​mw-editsection-divider">​ | </​span>​sửa mã nguồn<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Một ôtômat cây hữu hạn không xác định là đầy đủ nếu có ít nhất một luật chuyển cho mỗi cặp ký hiệu-trạng thái. Một trạng thái <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle q}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​q</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle q}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​06809d64fa7c817ffc7e323f85997f783dbdf71d"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.671ex; width:​1.07ex;​ height:​2.009ex;"​ alt="​{displaystyle q}"/></​span>​ là đến được nếu có một số hạng nền (ground term) <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​t</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle t}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt="​t"/></​span>​ sao cho có một phép biến đổi từ <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle t}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​t</​mi></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle t}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​65658b7b223af9e1acc877d848888ecdb4466560"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.338ex; width:​0.84ex;​ height:​2.009ex;"​ alt="​t"/></​span>​ đến <span class="​mwe-math-element"><​span class="​mwe-math-mathml-inline mwe-math-mathml-a11y"​ style="​display:​ none;"><​math xmlns="​http://​www.w3.org/​1998/​Math/​MathML"​ alttext="​{displaystyle q(t)}"><​semantics><​mrow class="​MJX-TeXAtom-ORD"><​mstyle displaystyle="​true"​ scriptlevel="​0"><​mi>​q</​mi><​mo stretchy="​false">​(</​mo><​mi>​t</​mi><​mo stretchy="​false">​)</​mo></​mstyle></​mrow><​annotation encoding="​application/​x-tex">​{displaystyle q(t)}</​annotation></​semantics></​math></​span><​img src="​https://​wikimedia.org/​api/​rest_v1/​media/​math/​render/​svg/​3b1f8079f76d0e8a89cf19db8fc43f34ec569d25"​ class="​mwe-math-fallback-image-inline"​ aria-hidden="​true"​ style="​vertical-align:​ -0.838ex; width:​3.718ex;​ height:​2.843ex;"​ alt="​{displaystyle q(t)}"/></​span>​. Một ôtômat cây hữu hạn là giản lược nếu mọi trạng thái của nó đều đến được.
 +</p>
 +<​h3><​span id="​.C4.90.E1.BB.8Bnh_l.C3.BD_b.C6.A1m"/><​span class="​mw-headline"​ id="​Định_lý_bơm">​Định lý bơm</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​sửa<​span class="​mw-editsection-divider">​ | </​span>​sửa mã nguồn<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​h3><​span id="​Bao_.C4.91.C3.B3ng"/><​span class="​mw-headline"​ id="​Bao_đóng">​Bao đóng</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​sửa<​span class="​mw-editsection-divider">​ | </​span>​sửa mã nguồn<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +<​p>​Lớp các ngôn ngữ cây có thể nhận dạng được là đóng với các phép hợp, bù và giao.
 +</p>
 +<​h3><​span id="​.C4.90.E1.BB.8Bnh_l.C3.BD_Myhill-Nerode"/><​span class="​mw-headline"​ id="​Định_lý_Myhill-Nerode">​Định lý Myhill-Nerode</​span><​span class="​mw-editsection"><​span class="​mw-editsection-bracket">​[</​span>​sửa<​span class="​mw-editsection-divider">​ | </​span>​sửa mã nguồn<​span class="​mw-editsection-bracket">​]</​span></​span></​h3>​
 +
 +
 +<​p>​Kiến thức trong trang này đều lấy từ chương một, sách "Tree automata techniques and applications"​ - http://​tata.gforge.inria.fr
 +</p>
 +
 +<​!-- ​
 +NewPP limit report
 +Parsed by mw1266
 +Cached time: 20181017030937
 +Cache expiry: 1900800
 +Dynamic content: false
 +CPU time usage: 0.112 seconds
 +Real time usage: 0.184 seconds
 +Preprocessor visited node count: 382/1000000
 +Preprocessor generated node count: 0/1500000
 +Post&#​8208;​expand include size: 10231/​2097152 bytes
 +Template argument size: 158/2097152 bytes
 +Highest expansion depth: 8/40
 +Expensive parser function count: 0/500
 +Unstrip recursion depth: 0/20
 +Unstrip post&#​8208;​expand size: 756/5000000 bytes
 +Number of Wikibase entities loaded: 0/400
 +Lua time usage: 0.028/​10.000 seconds
 +Lua memory usage: 1.19 MB/50 MB
 +--><​!--
 +Transclusion expansion time report (%,​ms,​calls,​template)
 +100.00% ​  ​82.614 ​     1 -total
 + ​66.73% ​  ​55.129 ​     1 B&#​7843;​n_m&#​7851;​u:​Ch&​uacute;​_th&​iacute;​ch_trong_b&​agrave;​i
 + ​43.80% ​  ​36.189 ​     2 B&#​7843;​n_m&#​7851;​u:​H&#​7897;​p_th&​ocirc;​ng_b&​aacute;​o
 + ​14.19% ​  ​11.722 ​     4 B&#​7843;​n_m&#​7851;​u:​C&#​7847;​n_ch&​uacute;​_th&​iacute;​ch
 + ​10.35% ​   8.547      1 B&#​7843;​n_m&#​7851;​u:​S&#​7917;​a_ch&#​7919;​a
 +  7.86%    6.497      1 B&#​7843;​n_m&#​7851;​u:​Wikify
 +  6.79%    5.607      2 B&#​7843;​n_m&#​7851;​u:​X&#​7917;​_l&​yacute;​_th&#​7875;​_lo&#​7841;​i
 +  4.80%    3.969      1 B&#​7843;​n_m&#​7851;​u:​Ambox
 +  3.65%    3.017      1 B&#​7843;​n_m&#​7851;​u:​Tham_kh&#​7843;​o
 +--><​!-- Saved in parser cache with key viwiki:​pcache:​idhash:​1265646-0!canonical!math=5 and timestamp 20181017030936 and revision id 26442552
 + ​--></​div><​noscript><​img src="​http://​vi.wikipedia.org/​wiki/​Special:​CentralAutoLogin/​start?​type=1x1"​ alt=""​ title=""​ width="​1"​ height="​1"​ style="​border:​ none; position: absolute;"/></​noscript></​div>​
 +
 +</​HTML>​
2228--t-mat-c-y-la-gi.txt · Last modified: 2018/11/07 17:11 (external edit)