generalizzando il lemma di pompaggio per stile UNIX espressioni regolari

Question

La maggior parte UNIX espressioni regolari hanno, oltre al consueto **, +, ?* operatori Un operatore backslash dove \1,\2,... partita tutto quello che è negli ultimi parentesi, così per esempio *L=(a*)b\1* corrisponda alla (non regolare) lingua *a^n b a^n*.

Da un lato, questo sembra essere piuttosto potente poiché è possibile creare (a*)b\1b\1 in modo che corrisponda alla lingua *a^n b a^n b a^n* che non può nemmeno essere riconosciuta da un automa di stack. D'altra parte, sono abbastanza sicuro che *a^n b^n* non possa essere espresso in questo modo.

Ho due domande:

1. Esiste una letteratura su questa famiglia di lingue (UNIX-y regolare). In particolare, esiste una versione del lemma di pompaggio per questi?
2. Qualcuno può provare, o smentire, che *a^n b^n* non può essere espresso in questo modo?

Answer 1

a^n b^n è CFL. La grammatica è

A -> aAb | e 

è possibile utilizzare il pompaggio lemma per RL di dimostrare A non è Rl

Answer 2

Ruby 1.9.1 supporta il seguente espressione regolare:

regex = %r{ (?<foo> a\g<foo>a | b\g<foo>b | c) }x 

p regex.match("aaacbbb") 
# the result is #<MatchData "c" foo:"c"> 

"Fun with Ruby 1.9 Regular Expressions" ha un esempio in cui egli in realtà organizza tutte le parti di una regex in modo che appaia come una grammatica context-free come segue:

sentence = %r{ 
    (?<subject> cat | dog | gerbil ){0} 
    (?<verb>  eats | drinks| generates){0} 
    (?<object> water | bones | PDFs  ){0} 
    (?<adjective> big | small | smelly ){0} 

    (?<opt_adj> (\g<adjective>\s)? ){0} 

    The\s\g<opt_adj>\g<subject>\s\g<verb>\s\g<opt_adj>\g<object> 
}x 

Penso che questo significhi che almeno il motore regex di Ruby 1.9.1, che è il motore regex di Oniguruma, è in realtà equivalente a una grammatica context-free, sebbene i gruppi di cattura non siano utili come un generatore di parser.

Ciò significa che "Pumping lemma for context-free languages" deve descrivere la classe di lingue riconoscibile dal motore regex di Ruby 1.9.1.

MODIFICA: Whoops! Ho incasinato, e non ho fatto un test importante che in realtà rende la mia risposta sopra totalmente sbagliata. Non cancellerò la risposta, perché è comunque un'informazione utile.

regex = %r{\A(?<foo> a\g<foo>a | b\g<foo>b | c)\Z}x 
#I added anchors for the beginning and end of the string 
regex.match("aaacbbb") 
#returns nil, indicating that no match is possible with recursive capturing groups. 

EDIT: Tornando a questo molti mesi dopo, ho appena scoperto che la mia prova in ultima modifica non era corretta. non dovrebbe corrispondere allo regex anche se regex funziona come una grammatica senza contesto.

Il test corretta dovrebbe essere su una stringa come "aabcbaa", e che non corrisponda alla espressione regolare:

regex = %r{\A(?<foo> a\g<foo>a | b\g<foo>b | c)\Z}x 
regex.match("aaacaaa") 
# => #<MatchData "aaacaaa" foo:"aaacaaa"> 
regex.match("aacaa") 
# => #<MatchData "aacaa" foo:"aacaa"> 
regex.match("aabcbaa") 
# => #<MatchData "aabcbaa" foo:"aabcbaa"> 

Answer 3

Probabilmente siete alla ricerca di

• Benjamin Carle e Paliath Narendran "On regolare estesa Espressioni" LNCS 5457
  • DOI:10.1007/978-3-642-00982-2_24
  • PDF extended abstract in http://hal.archives-ouvertes.fr/docs/00/17/60/43/PDF/notes_on_extended_regexp.pdf
• C. Campeanu, K. Salomaa, S. Yu: uno studio formale di espressioni regolari pratiche, International Journal of Fondamenti di Informatica, vol. 14 (2003) 1007 - 1018.
  • DOI:10.1142/S012905410300214X

e, naturalmente, seguire i loro citazioni in avanti e indietro per trovare più la letteratura su questo argomento.