File:RepFreeDeriv.pdf

Size of this JPG preview of this PDF file: 799 × 77 pixels. Other resolution: 1,504 × 145 pixels.

Original file ‎(1,504 × 145 pixels, file size: 20 KB, MIME type: application/pdf)

Captions

English

Add a one-line explanation of what this file represents

Summary[edit]

DescriptionRepFreeDeriv.pdf	English: It is an NP hard problem to check whether a given string $\omega$ can be derived from a given regular grammar ${\mathcal {G}}$ such that no nonterminal symbol is used multiply, or, equivalently, if $\omega$ can be accepted by a nondeterministic finite automaton without visiting any state repeatedly. This can be proved by constructing a string $\omega$ and a grammar ${\mathcal {G}}$ from a given formula $\kappa$ in conjunctive normal form such that $\omega$ can be derived repetition-free from ${\mathcal {G}}$ if, and only if, $\kappa$ is satisfiable (using the NP-hardness of the 3-satisfiability problem). The picture shows, for the example formula $(x_{1}\lor \lnot x_{2}\lor x_{4})\land (x_{2}\lor x_{3}\lor \lnot x_{4})\land (\lnot x_{1}\lor \lnot x_{2}\lor x_{4})$ , the structure of the corresponding grammar ${\mathcal {G}}$ . The grammar details are given below. (The picture can also be interpreted as a nondeterministic finite automaton with initial state $S_{0}$ , when the omitted edge labels are supplemented as follows: " $a$ " on every edge left of $S_{4}$ ; " $b$ " on the single edge from $S_{4}$ to $T_{0}$ ; " $c$ " on every edge leaving $T_{0}$ , $T_{1}$ , or $T_{2}$ ; " $e$ " on every edge entering $T_{1}$ , $T_{2}$ , or $T_{3}$ ; and " $d$ " on the single edge from $T_{3}$ to the -undepicted- unique accepting state.) Since the formula consists of 3 conjuncts and uses 4 variables, $\omega$ is chosen to be $a^{(3+1)\cdot 4}b(ce)^{3}d$ . Informally, in the left part, to get from $S_{0}$ to $S_{4}$ , an appropriate choice of the upper / lower path has to made at each $S_{i}$ , corresponding to an assignment of true / false for variable $x_{i+1}$ . In the right part, at each $T_{j}$ an appropriate path (upper / middle / lower) has to chosen, corresponding to the choice of a satisfying literal for the $(j+1)$ ^th conjunct. The nonterminal symbols a distributed in such a way that a repetition occurs if, and only if, a literal is chosen in the right part that is not satisfying according to the variable assignment from the left part. Thus, a repetition-free path from $S_{0}$ to $T_{3}$ exists if, and only if, an assignment of truth values to variables exists such that all conjuncts are satisfied. For details, see sect.3 of Jochen Burghardt (Feb 2016) Repetition-Free Derivability from a Regular Grammar is NP-Hard
Date	21 February 2021
Source	Own work
Author	Jochen Burghardt

Detailled regular grammar

${\begin{array}{|l|l|l|}\hline {\begin{array}{lclclcl}S_{0}&::=&aX_{11}&\mid &a{\overline {X}}_{11}\\X_{11}&::=&aX_{12}&\mid &eT_{1}\\X_{12}&::=&aX_{13}\\X_{13}&::=&aS_{1}\\S_{1}&::=&aX_{21}&\mid &a{\overline {X}}_{21}\\X_{21}&::=&aX_{22}\\X_{22}&::=&aX_{23}&\mid &eT_{2}\\X_{23}&::=&aS_{2}\\S_{2}&::=&aX_{31}&\mid &a{\overline {X}}_{31}\\X_{31}&::=&aX_{32}&&\\X_{32}&::=&aX_{33}&\mid &eT_{2}\\X_{33}&::=&aS_{3}&&\\S_{3}&::=&aX_{41}&\mid &a{\overline {X}}_{41}\\X_{41}&::=&aX_{42}&\mid &eT_{1}\\X_{42}&::=&aX_{43}&&\\X_{43}&::=&aS_{4}&\mid &eT_{3}\\S_{4}&::=&bT_{0}\\\end{array}}&{\begin{array}{lclcl}\\{\overline {X}}_{11}&::=&a{\overline {X}}_{12}\\{\overline {X}}_{12}&::=&a{\overline {X}}_{13}\\{\overline {X}}_{13}&::=&aS_{1}&\mid &eT_{3}\\\\{\overline {X}}_{21}&::=&a{\overline {X}}_{22}&\mid &eT_{1}\\{\overline {X}}_{22}&::=&a{\overline {X}}_{23}\\{\overline {X}}_{23}&::=&aS_{2}&\mid &eT_{3}\\\\{\overline {X}}_{31}&::=&a{\overline {X}}_{32}&&\\{\overline {X}}_{32}&::=&a{\overline {X}}_{33}&&\\{\overline {X}}_{33}&::=&aS_{3}&&\\\\{\overline {X}}_{41}&::=&a{\overline {X}}_{42}&&\\{\overline {X}}_{42}&::=&a{\overline {X}}_{43}&\mid &eT_{2}\\{\overline {X}}_{43}&::=&aS_{4}&&\\\end{array}}&{\begin{array}{lclclcl}\\\\\\\\\\\\\\\\\\\\\\\\T_{0}&::=&cX_{11}&\mid &c{\overline {X}}_{21}&\mid &cX_{41}\\T_{1}&::=&cX_{22}&\mid &cX_{3}2&\mid &c{\overline {X}}_{42}\\T_{2}&::=&c{\overline {X}}_{13}&\mid &c{\overline {X}}_{23}&\mid &cX_{43}\\T_{3}&::=&d&&&&\\\end{array}}\\\hline \end{array}}$

LaTeX source

\documentclass[12pt]{article}
\usepackage[pdftex]{color}
\usepackage[paperwidth=255mm,paperheight=25mm]{geometry}
\setlength{\topmargin}{-36mm}
\setlength{\textwidth}{255mm}
\setlength{\textheight}{25mm}
\setlength{\oddsidemargin}{-23mm}
\setlength{\parindent}{0cm}
\setlength{\unitlength}{1mm}
\pagestyle{empty}
\begin{document}

\definecolor{coEqvA}    {rgb}{0.80,0.00,0.00}
\definecolor{coEqvB}    {rgb}{0.40,0.00,0.00}
\definecolor{coEqvC}    {rgb}{0.00,0.80,0.00}
\definecolor{coEqvD}    {rgb}{0.00,0.40,0.00}
\definecolor{coEqvE}    {rgb}{0.00,0.00,0.80}
\definecolor{coEqvF}    {rgb}{0.00,0.00,0.40}
\definecolor{coEqvG}    {rgb}{0.00,0.80,0.80}
\definecolor{coEqvH}    {rgb}{0.00,0.40,0.40}
\newcommand{\0}[1]{\textcolor{coEqvA}{#1}}
\newcommand{\1}[1]{\textcolor{coEqvB}{#1}}
\newcommand{\2}[1]{\textcolor{coEqvC}{#1}}
\newcommand{\3}[1]{\textcolor{coEqvD}{#1}}
\newcommand{\4}[1]{\textcolor{coEqvE}{#1}}
\newcommand{\5}[1]{\textcolor{coEqvF}{#1}}
\newcommand{\6}[1]{\textcolor{coEqvG}{#1}}
\newcommand{\7}[1]{\textcolor{coEqvH}{#1}}

\begin{picture}(250,20)
        %\put(0,0){\makebox(0,0){$+$}}
        %\put(250,20){\makebox(0,0){$+$}}
\put(3,10){\makebox(0,0){$S_0$}}
\put(5,10){\vector(1,1){4}}
\put(5,10){\vector(1,-1){4}}
%
\put(12,15){\makebox(0,0){$\0{X_{11}}$}}
\put(12,5){\makebox(0,0){$\1{\overline{X}_{11}}$}}
\put(15,15){\vector(1,0){2}}
\put(15,5){\vector(1,0){2}}
\put(20,15){\makebox(0,0){$\0{X_{12}}$}}
\put(20,5){\makebox(0,0){$\1{\overline{X}_{12}}$}}
\put(23,15){\vector(1,0){2}}
\put(23,5){\vector(1,0){2}}
\put(28,15){\makebox(0,0){$\0{X_{13}}$}}
\put(28,5){\makebox(0,0){$\1{\overline{X}_{13}}$}}
\put(31,14){\vector(1,-1){4}}
\put(31,6){\vector(1,1){4}}
%
\put(37,10){\makebox(0,0){$S_1$}}
\put(39,10){\vector(1,1){4}}
\put(39,10){\vector(1,-1){4}}
\put(46,15){\makebox(0,0){$\2{X_{21}}$}}
\put(46,5){\makebox(0,0){$\3{\overline{X}_{21}}$}}
\put(49,15){\vector(1,0){2}}
\put(49,5){\vector(1,0){2}}
\put(54,15){\makebox(0,0){$\2{X_{22}}$}}
\put(54,5){\makebox(0,0){$\3{\overline{X}_{22}}$}}
\put(57,15){\vector(1,0){2}}
\put(57,5){\vector(1,0){2}}
\put(62,15){\makebox(0,0){$\2{X_{23}}$}}
\put(62,5){\makebox(0,0){$\3{\overline{X}_{23}}$}}
\put(65,14){\vector(1,-1){4}}
\put(65,6){\vector(1,1){4}}
%
\put(71,10){\makebox(0,0){$S_2$}}
\put(73,10){\vector(1,1){4}}
\put(73,10){\vector(1,-1){4}}
\put(80,15){\makebox(0,0){$\4{X_{31}}$}}
\put(80,5){\makebox(0,0){$\5{\overline{X}_{31}}$}}
\put(83,15){\vector(1,0){2}}
\put(83,5){\vector(1,0){2}}
\put(88,15){\makebox(0,0){$\4{X_{32}}$}}
\put(88,5){\makebox(0,0){$\5{\overline{X}_{32}}$}}
\put(91,15){\vector(1,0){2}}
\put(91,5){\vector(1,0){2}}
\put(96,15){\makebox(0,0){$\4{X_{33}}$}}
\put(96,5){\makebox(0,0){$\5{\overline{X}_{33}}$}}
\put(99,14){\vector(1,-1){4}}
\put(99,6){\vector(1,1){4}}
%
\put(105,10){\makebox(0,0){$S_3$}}
\put(107,10){\vector(1,1){4}}
\put(107,10){\vector(1,-1){4}}
\put(114,15){\makebox(0,0){$\6{X_{41}}$}}
\put(114,5){\makebox(0,0){$\7{\overline{X}_{41}}$}}
\put(117,15){\vector(1,0){2}}
\put(117,5){\vector(1,0){2}}
\put(122,15){\makebox(0,0){$\6{X_{42}}$}}
\put(122,5){\makebox(0,0){$\7{\overline{X}_{42}}$}}
\put(125,15){\vector(1,0){2}}
\put(125,5){\vector(1,0){2}}
\put(130,15){\makebox(0,0){$\6{X_{43}}$}}
\put(130,5){\makebox(0,0){$\7{\overline{X}_{43}}$}}
\put(133,14){\vector(1,-1){4}}
\put(133,6){\vector(1,1){4}}
%
\put(139,10){\makebox(0,0){$S_4$}}
\put(142,10){\vector(1,0){5}}
\put(149,10){\makebox(0,0){$T_0$}}
\put(152,10){\vector(2,1){10}}
\put(152,10){\vector(1,0){10}}
\put(152,10){\vector(2,-1){10}}
\put(165,15){\makebox(0,0){$\0{X_{11}}$}}
\put(165,10){\makebox(0,0){$\3{\overline{X}_{21}}$}}
\put(165,5){\makebox(0,0){$\6{X_{41}}$}}
\put(168,15){\vector(2,-1){10}}
\put(168,10){\vector(1,0){10}}
\put(168,5){\vector(2,1){10}}
%
\put(181,10){\makebox(0,0){$T_1$}}
\put(184,10){\vector(2,1){10}}
\put(184,10){\vector(1,0){10}}
\put(184,10){\vector(2,-1){10}}
\put(197,15){\makebox(0,0){$\2{X_{22}}$}}
\put(197,10){\makebox(0,0){$\4{X_{32}}$}}
\put(197,5){\makebox(0,0){$\7{\overline{X}_{42}}$}}
\put(200,15){\vector(2,-1){10}}
\put(200,10){\vector(1,0){10}}
\put(200,5){\vector(2,1){10}}
%
\put(213,10){\makebox(0,0){$T_2$}}
\put(216,10){\vector(2,1){10}}
\put(216,10){\vector(1,0){10}}
\put(216,10){\vector(2,-1){10}}
\put(229,15){\makebox(0,0){$\1{\overline{X}_{13}}$}}
\put(229,10){\makebox(0,0){$\3{\overline{X}_{23}}$}}
\put(229,5){\makebox(0,0){$\6{X_{43}}$}}
\put(232,15){\vector(2,-1){10}}
\put(232,10){\vector(1,0){10}}
\put(232,5){\vector(2,1){10}}
%
\put(245,10){\makebox(0,0){$T_3$}}
%
\end{picture}
\end{document}

Licensing[edit]

I, the copyright holder of this work, hereby publish it under the following license:

This file is licensed under the Creative Commons Attribution-Share Alike 4.0 International license.

You are free:

to share – to copy, distribute and transmit the work
to remix – to adapt the work

Under the following conditions:

attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.

File history

Click on a date/time to view the file as it appeared at that time.

	Date/Time	Thumbnail	Dimensions	User	Comment
current	12:32, 21 February 2021		1,504 × 145 (20 KB)	Jochen Burghardt (talk \| contribs)	Uploaded own work with UploadWizard

You cannot overwrite this file.

File usage on Commons

The following page uses this file:

User:Drogosław/Typewriters/2021 February

Metadata

This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.

Software used	TeX
Conversion program	pdfTeX-1.40.18
Encrypted	no
Page size	722.835 x 70.866 pts
Version of PDF format	1.5

File:RepFreeDeriv.pdf

Captions

Captions

Summary[edit]

Licensing[edit]

File history

File usage on Commons

Metadata

Structured data

Items portrayed in this file

depicts

creator

some value

copyright status

copyrighted

copyright license

Creative Commons Attribution-ShareAlike 4.0 International

inception

21 February 2021

source of file

original creation by uploader

media type

application/pdf

Navigation menu

File:RepFreeDeriv.pdf

Captions

Captions

Summary[edit]

Licensing[edit]

File history

File usage on Commons

Metadata

Navigation menu

Search