Datei:RegSubsetNP.pdf
Größe der JPG-Vorschau dieser PDF-Datei: 430 × 599 Pixel. Weitere Auflösungen: 172 × 240 Pixel | 344 × 480 Pixel | 825 × 1.150 Pixel
Originaldatei (825 × 1.150 Pixel, Dateigröße: 11 KB, MIME-Typ: application/pdf)
Diese Datei und die Informationen unter dem roten Trennstrich werden aus dem zentralen Medienarchiv Wikimedia Commons eingebunden.
Beschreibung
| Beschreibung |
English: Example to demonstrate that the subset property for regular languages is NP-hard. Given a propositional formula in disjunctive normal form in n variables , a corresponding nondeterministic finite automaton A can be constructed such that it accepts the regular language {0,1}n if, and only if, the formula is true for all variable assignments. Therefore, the NP-hard problem of deciding the universal validity of a propositional formula in disjunctive normal form can be reduced to the problem of deciding whether {0,1}n ⊆ L(A).
The shown example uses the formula abc+abd+abc+abd+bcd+acd+bcd+acd in n=4 variables. The corresponding automaton A is shown in the upper part of the picture; unlabelled transitions are ε-transitions. Each summand in the formula corresponds to one "row" in the automaton A; e.g. the last one, acd, corresponds to the bottommost row of A; the summand is valid exactly for those variable assignments that correspond to a string from the row's accepted language, i.e. {1101,1001} for this row. The language {0,1}n is regular since it is accepted by the the automaton B shown at the lower picture part. |
| Datum | |
| Quelle | Eigenes Werk |
| Urheber | Jochen Burghardt |
| Andere Versionen | File:RegSubsetNP svg.svg |
LaTeX source code
|
|---|
\documentclass[12pt]{article}
\setlength{\unitlength}{1mm}
\usepackage[pdftex]{color}
\usepackage[paperwidth=140\unitlength,paperheight=195\unitlength]{geometry}
\setlength{\topmargin}{-36mm}
\setlength{\textwidth}{140\unitlength}
\setlength{\textheight}{195\unitlength}
\setlength{\oddsidemargin}{-23mm}
\setlength{\parindent}{0cm}
\pagestyle{empty}
% colors
\definecolor{cS} {rgb}{0.00,0.00,0.40} % state
\definecolor{cE} {rgb}{0.40,0.40,0.40} % epsilon transition
\definecolor{cO} {rgb}{0.40,0.00,0.00} % 0 transition
\definecolor{cI} {rgb}{0.00,0.40,0.00} % 1 transition
\begin{document}
\begin{picture}(135,190)
% start state
\thicklines
\textcolor{cS}{\put(0.000,100.000){\vector(1,0){5}}}%
\textcolor{cS}{\put(6.000,100.000){\circle*{2.000}}}%
% eps-transitions to disjoints
\textcolor{cE}{\put(6.000,100.000){\vector(1,4){20.000}}}%
\textcolor{cE}{\put(6.000,100.000){\vector(1,3){20.000}}}%
\textcolor{cE}{\put(6.000,100.000){\vector(1,2){20.000}}}%
\textcolor{cE}{\put(6.000,100.000){\vector(1,1){20.000}}}%
\textcolor{cE}{\put(6.000,100.000){\vector(1,0){20.000}}}%
\textcolor{cE}{\put(6.000,100.000){\vector(1,-1){20.000}}}%
\textcolor{cE}{\put(6.000,100.000){\vector(1,-2){20.000}}}%
\textcolor{cE}{\put(6.000,100.000){\vector(1,-3){20.000}}}%
\textcolor{cS}{\put(27.000,180.000){\circle*{2.000}}}%
\textcolor{cS}{\put(27.000,160.000){\circle*{2.000}}}%
\textcolor{cS}{\put(27.000,140.000){\circle*{2.000}}}%
\textcolor{cS}{\put(27.000,120.000){\circle*{2.000}}}%
\textcolor{cS}{\put(27.000,100.000){\circle*{2.000}}}%
\textcolor{cS}{\put(27.000,80.000){\circle*{2.000}}}%
\textcolor{cS}{\put(27.000,60.000){\circle*{2.000}}}%
\textcolor{cS}{\put(27.000,40.000){\circle*{2.000}}}%
% disjoint a b c
\textcolor{cI}{\put(27.000,180.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(37.000,183.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(37.000,184.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(47.000,180.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(48.000,180.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(58.000,183.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(58.000,184.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(68.000,180.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(69.000,180.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(79.000,183.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(79.000,184.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(89.000,180.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(90.000,180.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(100.000,183.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(100.000,184.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(90.000,179.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(100.000,177.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(100.000,176.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(110.000,180.000){\circle*{2.000}}}%
% disjoint a \b \d
\textcolor{cI}{\put(27.000,160.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(37.000,163.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(37.000,164.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(47.000,160.000){\circle*{2.000}}}%
%
\textcolor{cO}{\put(48.000,159.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(58.000,157.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(58.000,156.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(68.000,160.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(69.000,160.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(79.000,163.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(79.000,164.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(69.000,159.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(79.000,157.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(79.000,156.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(89.000,160.000){\circle*{2.000}}}%
%
\textcolor{cO}{\put(90.000,159.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(100.000,157.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(100.000,156.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(110.000,160.000){\circle*{2.000}}}%
% disjoint \a \b \c
\textcolor{cO}{\put(27.000,139.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(37.000,137.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(37.000,136.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(47.000,140.000){\circle*{2.000}}}%
%
\textcolor{cO}{\put(48.000,139.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(58.000,137.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(58.000,136.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(68.000,140.000){\circle*{2.000}}}%
%
\textcolor{cO}{\put(69.000,139.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(79.000,137.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(79.000,136.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(89.000,140.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(90.000,140.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(100.000,143.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(100.000,144.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(90.000,139.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(100.000,137.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(100.000,136.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(110.000,140.000){\circle*{2.000}}}%
% disjoint \a b d
\textcolor{cO}{\put(27.000,119.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(37.000,117.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(37.000,116.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(47.000,120.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(48.000,120.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(58.000,123.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(58.000,124.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(68.000,120.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(69.000,120.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(79.000,123.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(79.000,124.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(69.000,119.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(79.000,117.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(79.000,116.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(89.000,120.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(90.000,120.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(100.000,123.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(100.000,124.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(110.000,120.000){\circle*{2.000}}}%
% disjoint \b c d
\textcolor{cI}{\put(27.000,100.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(37.000,103.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(37.000,104.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(27.000,99.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(37.000,97.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(37.000,96.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(47.000,100.000){\circle*{2.000}}}%
%
\textcolor{cO}{\put(48.000,99.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(58.000,97.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(58.000,96.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(68.000,100.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(69.000,100.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(79.000,103.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(79.000,104.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(89.000,100.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(90.000,100.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(100.000,103.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(100.000,104.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(110.000,100.000){\circle*{2.000}}}%
% disjoint \a c \d
\textcolor{cO}{\put(27.000,79.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(37.000,77.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(37.000,76.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(47.000,80.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(48.000,80.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(58.000,83.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(58.000,84.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(48.000,79.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(58.000,77.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(58.000,76.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(68.000,80.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(69.000,80.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(79.000,83.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(79.000,84.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(89.000,80.000){\circle*{2.000}}}%
%
\textcolor{cO}{\put(90.000,79.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(100.000,77.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(100.000,76.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(110.000,80.000){\circle*{2.000}}}%
% disjoint b \c \d
\textcolor{cI}{\put(27.000,60.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(37.000,63.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(37.000,64.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(27.000,59.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(37.000,57.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(37.000,56.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(47.000,60.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(48.000,60.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(58.000,63.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(58.000,64.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(68.000,60.000){\circle*{2.000}}}%
%
\textcolor{cO}{\put(69.000,59.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(79.000,57.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(79.000,56.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(89.000,60.000){\circle*{2.000}}}%
%
\textcolor{cO}{\put(90.000,59.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(100.000,57.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(100.000,56.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(110.000,60.000){\circle*{2.000}}}%
% disjoint a \c d
\textcolor{cI}{\put(27.000,40.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(37.000,43.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(37.000,44.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(47.000,40.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(48.000,40.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(58.000,43.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(58.000,44.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(48.000,39.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(58.000,37.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(58.000,36.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(68.000,40.000){\circle*{2.000}}}%
%
\textcolor{cO}{\put(69.000,39.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(79.000,37.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(79.000,36.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(89.000,40.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(90.000,40.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(100.000,43.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(100.000,44.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cS}{\put(110.000,40.000){\circle*{2.000}}}%
% eps-transitions from disjoints
\textcolor{cE}{\put(111.000,180.000){\vector(1,-4){19.800}}}%
\textcolor{cE}{\put(111.000,160.000){\vector(1,-3){19.800}}}%
\textcolor{cE}{\put(111.000,140.000){\vector(1,-2){19.700}}}%
\textcolor{cE}{\put(111.000,120.000){\vector(1,-1){19.600}}}%
\textcolor{cE}{\put(111.000,100.000){\vector(1,0){19.500}}}%
\textcolor{cE}{\put(111.000,80.000){\vector(1,1){19.600}}}%
\textcolor{cE}{\put(111.000,60.000){\vector(1,2){19.700}}}%
\textcolor{cE}{\put(111.000,40.000){\vector(1,3){19.800}}}%
% final state
\textcolor{cS}{\put(132.000,100.000){\circle*{2.000}}}%
\textcolor{cS}{\put(132.000,100.000){\circle{3.000}}}%
% full language
\textcolor{cS}{\put(21.000,7.000){\vector(1,0){5.000}}}%
\textcolor{cS}{\put(27.000,7.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(27.000,7.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(37.000,10.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(37.000,11.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(27.000,6.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(37.000,4.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(37.000,3.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(47.000,7.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(48.000,7.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(58.000,10.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(58.000,11.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(48.000,6.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(58.000,4.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(58.000,3.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(68.000,7.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(69.000,7.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(79.000,10.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(79.000,11.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(69.000,6.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(79.000,4.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(79.000,3.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(89.000,7.000){\circle*{2.000}}}%
%
\textcolor{cI}{\put(90.000,7.500){\line(4,1){10.000}}}%
\textcolor{cI}{\put(100.000,10.000){\vector(4,-1){10.000}}}%
\textcolor{cI}{\put(100.000,11.000){\makebox(0.000,0.000)[b]{$1$}}}%
\textcolor{cO}{\put(90.000,6.500){\line(4,-1){10.000}}}%
\textcolor{cO}{\put(100.000,4.000){\vector(4,1){10.000}}}%
\textcolor{cO}{\put(100.000,3.000){\makebox(0.000,0.000)[t]{$0$}}}%
\textcolor{cS}{\put(111.000,7.000){\circle*{2.000}}}%
\textcolor{cS}{\put(111.000,7.000){\circle{3.000}}}%
\end{picture}
\end{document}
|
Lizenz
Ich, der Urheber dieses Werkes, veröffentliche es unter der folgenden Lizenz:
Diese Datei ist lizenziert unter der Creative-Commons-Lizenz „Namensnennung – Weitergabe unter gleichen Bedingungen 4.0 international“.
- Dieses Werk darf von dir
- verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
- neu zusammengestellt werden – abgewandelt und bearbeitet werden
- Zu den folgenden Bedingungen:
- Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.
- Weitergabe unter gleichen Bedingungen – Wenn du das Material wiedermischst, transformierst oder darauf aufbaust, musst du deine Beiträge unter der gleichen oder einer kompatiblen Lizenz wie das Original verbreiten.
Dateiversionen
Klicke auf einen Zeitpunkt, um diese Version zu laden.
| Version vom | Vorschaubild | Maße | Benutzer | Kommentar | |
|---|---|---|---|---|---|
| aktuell | 21:01, 6. Jan. 2016 |  | 825 × 1.150 (11 KB) | Jochen Burghardt | User created page with UploadWizard |
Dateiverwendung
Keine Seiten verwenden diese Datei.