I AE I nte rna t io na l J o urna l o f   Art if icia l In t ellig ence   ( I J - AI )   Vo l.   6 ,   No .   3 Sep tem b er   2 0 1 7 ,   p p .   1 0 0 ~ 1 1 1   I SS N:  2252 - 8938 ,   D OI : 1 0 . 1 1 5 9 1 /i j ai. v 6 . i3 . p p 1 0 0 - 1 1 1          100       J o ur na l ho m ep a g e h ttp : //ia e s jo u r n a l.c o m/o n lin e/in d ex . p h p /I J AI   G ene tic  Alg o rith m   for  G ra mm a r I nduction a nd  Rul es  Verific a tion  t hro ug h a PDA  Si m ul a tor       H a ri  M o ha n P a nd ey   De p a rt m e n o f   Co m p u ter S c ien c e   a n d   E n g in e e rin g ,   A m it y   Un iv e rsi ty ,   In d ia       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   J u n   6 ,   2 0 1 7   R ev i s ed   A ug   8 ,   2 0 1 7   A cc ep ted   A u g   2 2 ,   2 0 1 7       T h e   f o c u o f   th is  p a p e is  t o w a rd d e v e lo p in g   a   g ra m m a ti c a in f e re n c e   s y ste m   u se a   g e n e ti c   a lg o rit h m   (GA ),   h a a   p o w e r f u g lo b a e x p lo ra ti o n   c a p a b il it y   th a c a n   e x p lo it   th e   o p ti m u m   o ff sp rin g .   T h e   i m p le m e n ted   s y ste m   ru n i n   tw o   p h a se s:  f irst,   g e n e ra ti o n   o f   g ra m m a ru les   a n d   v e rif ica ti o n   a n d   th e n   a p p li e t h e   GA ‟s  o p e ra ti o n   t o   o p ti m ize   th e   ru les .   A   p u s h d o wn   a u t o m a ta   sim u lato h a b e e n   d e v e lo p e d ,   w h ich   p a rse   th e   train in g   d a ta  o v e th e   g ra m m a r‟s  ru les .   A n   in v e rted   m u tatio n   w it h   r a n d o m   m a s k   a n d   th e n   „X OR‟   o p e ra to r   h a b e e n   a p p li e d   in tro d u c e d iv e rsity   in   th e   p o p u lati o n ,   h e lp s   th e   GA   n o to   g e trap p e d   a lo c a o p ti m u m .   T a g u c h m e th o d   h a b e e n   in c o rp o ra ted   t o   t u n e   t h e   p a ra m e ters   m a k e th e   p ro p o se d   a p p r o a c h   m o re   ro b u st,  sta ti stica ll y   so u n d   a n d   q u ick ly   c o n v e rg e n t.   T h e   p e r f o r m a n c e   o f   th e   p ro p o se d   sy ste m   h a b e e n   c o m p a re d   w it h c las si c a GA ,   ra n d o m   o ff sp rin g   GA   a n d   c ro w d in g   a lg o rit h m s.  O v e ra ll ,   a   g ra m m a ti c a in fe re n c e   s y ste m   h a s   b e e n   d e v e lo p e d   th a e m p lo y s a P DA   si m u lato f o v e ri f ica ti o n.   K ey w o r d :   C o n te x t f r ee   g r a m m ar   Gen etic  al g o r ith m   Gr a m m ar   in d u ct io n   P ar s in g   P u s h d o w n   a u to m a ta     Co p y rig h ©   2 0 1 7   In stit u te o A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e   Al rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Har i M o h an   P an d e y ,     Dep ar t m en t o f   C o m p u ter   Sc ie n ce   an d   E n g i n ee r in g ,   ASET ,   Am it y   U n i v er s it y ,   Secto r   1 2 5 ,   No id a,   U. P .   I n d ia .   E m ail:  h ar i0 4 to p @ y ah o o . co . in       1.   I NT RO D UCT I O N     T h C o n te x f r ee   g r a m m ar s   ( C FG)   ( B NF  Gr a m m ar s )   h av e   b ee n   u s ed   ex ten s i v el y   to   d escr ib th e   s y n ta x   o f   p r o g r a m m i n g   la n g u ag es  a n d   n at u r a la n g u a g es.  P ar s in g   al g o r ith m s   f o r   C FG s   p l a y   s i g n i f ican r o le   in   th i m p le m en ta tio n   o f   co m p iler s   an d   in ter p r eter s   f o r   th p r o g r am m i n g   lan g u a g e s   an d   o f   p r o g r am s ,   w h ic h   “u n d er s ta n d ”  o r   tr an s late  th e   n atu r al  la n g u a g es.  T h er ex is t w o   d i f f er e n t y p e s   o f   p a r s er to p   d o w n   a n d   b o tto m   u p   p ar s er .   Sev er al  g o o d   alg o r ith m s   w er p r o p o s ed   in   liter at u r es  co n d u ct  s eq u e n tial  p ar s i n g   o f   t h e   co n tex f r ee   lan g u a g e s   ( C F L s ) .   So m o f   t h p o p u lar   p ar s in g   al g o r ith m s   ar C YK  p ar s i n g   [ 1 ,   2 ] E ar ley s   p ar s in g   [ 3 ] ,   an d   T o m ita  p ar s i n g   [ 1 5 ] .   T h er ar m a n y   o th er   s tan d ar d   p ar s in g   al g o r ith m s   al s o   av ailab le,   w h ic h   in cl u d o p er ato r   p r ec ed en ce   p ar s in g ,   p r ed ictiv p ar s i n g ,   r ec u r s i v d escen p ar s i n g ,   n o n - r ec u r s i v d escen t   p ar s in g ,   L R   p ar s i n g ,   an d   L AL R   p ar s i n g   [ 1 6 ] .   No am   C h o m s k y   ( 1 9 5 6 )   p r esen ted   class i f icatio n   s ch e m k n o w n   as  th C h o m s k y   h ier ar ch y   [ 1 7 ] .   T h class i f icatio n   s c h e m p r o p o s ed   is   co n n ec ted   to   th class i f icatio n   o f   au to m a ta  as  s h o w n   in   t h Fig u r 1 ,   w h ic h   ca n   b u s ed   to   r ec o g n ize  s p ec if ic  lan g u ag e   as  w ell  as  th e   g r a m m ar   u s ed   to   r ec o g n ize  th e m .   T h p r o b lem   o f   r ec o g n iz in g   lan g u a g ca n   b e x p lain ed   as:  let   L   b an y   lan g u ag o v er   a n   alp h ab et ,   th p r o b le m   is   to   d esig n   a n   a u to m ata   M th at  ac ce p an   i n p u s eq u en ce   in * .   T h M o n l y   ac ce p t th in p u t seq u e n ce   in   * if   th e y   ar v a lid   ele m e n t o f L ,   o th er w i s r ej ec ts ”.   Fig u r 1   d ep icts   th at   ea ch   cla s s   o f   la n g u a g i n   t h C h o m s k y   h ier ar ch y   is   g e n er ated   b y   s p ec if ic  t y p e   o f   g r a m m ar ,   w h ic h   w ill  t h en   r ec o g n ize  b y   an   ap p r o p r iate  ty p o f   au to m ata.   Mo v i n g   u p   in   th h ier ar ch y   o f   t h e   lan g u a g es,  t h t y p o f   au to m ata  r eq u ir ed   to   r ec o g n ize  th lan g u ag is   c h alle n g in g ,   w h er ea s   t h t y p o f   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       Gen etic  A lg o r ith fo r   Gra mm a r   I n d u ctio n   a n d   R u les V erif ica tio n   th r o u g h   a ...   ( Ha r i Mo h a n   P a n d ey )   101   g r a m m ar   n ee d ed   to   cr ea te  th lan g u a g b ec o m es   m o r g en er al.   On ca n   s ee   t h at  T y p 2   lan g u a g es,  g en er ated   b y   th C FG,  ar t h clas s   o f   lan g u a g es  t h at  ca n   b r ec o g n i ze d   b y   p u s h d o w n   au to m ata  ( eq u iv ale n to   f i n ite   au to m ata) ,   h av a n   u n b o u n d ed   s tack   a v ailab le.           Fig u r 1 .   C h o m s k y   h ier ar ch y       Gr a m m atica i n f er e n ce   ( GI )   o r   g r a m m ar   lear n i n g   d ea ls   w ith   id ea lized   lear n in g   p r o ce d u r to   ac q u ir e   g r a m m ar s   o n   t h b asis   o f   t h ev id en ce   ab o u th la n g u a g es   [ 4 - 6 ] ,   w as  e x te n s i v el y   s t u d ied   in   [ 6 - 1 4 ]   d u to   its   w id f ield s   o f   ap p licatio n s   to   s o lv t h p ar ticle  p r o b lem s .   I n   GI   p r o ce s s ,   an   in d iv id u al  g r am m ar   r u le  n ee d s   to   b v er if ied   u s i n g   a n   i n p u s t r in g   o f   s p ec if ic   lan g u ag e   o v er   f in i te  s tate   co n tr o ller ,   w h er ea s   p u s h d o wn   au to m ato n   is   u s ed   to   g e n er ate  th eq u i v ale n t p r o lif e r atio n   f o r   th lan g u a g e.   T h is   p ap er   p r esen ts   GI   alg o r ith m   co m b i n es  w it h   t h g e n eti alg o r ith m   ( G A ) ,   w h ic h   h as  a   p o w er f u l   g lo b al  ex p lo r atio n   ca p ab ilit y .   A   P D A   s i m u lato r   h as  b ee n   i m p le m e n ted   i n   th co m p u tati o n al  ex p er i m e n t h at   e m p lo y s   r ec u r s iv m eth o d   f o r   th p ar s in g   th at  r es u lt s   in   ter m s   o f   ac ce p ta n ce   o r   r ej ec tio n   o f   th s tr in g .   T h p r o ce d u r f o r   th P D A   s i m u lato r   h as  b ee n   i m p le m e n ted   an d   e x p la in ed   w i th   th e   h elp   o f   e x a m p les.   T h au th o r   h a s   i m p le m e n ted   t w o   p o in ts   c u cr o s s o v er   b ased   c y clic  cr o s s o v er   an d   i n v er ted   m u tat io n   w i th   r an d o m   o f f s p r i n g   th e n   ap p lie d   XO R   o p er atio n   f o r   t h r e p r o d u ctio n .   T h r ep r o d u ctio n   o p er ato r s   em p lo y ed   in tr o d u ce s   d iv er s it y   i n   t h p o p u latio n   h elp s   t h GI G A   to   ex p lo r th s ea r ch   s p ac ad eq u atel y .   T h au th o r   h a s   co m p ar ed   t h p er f o r m an ce   o f   th e   p r o p o s ed   GI GA  w it h   t h r ee   ex i s ti n g   al g o r ith m s   n a m el y   cla s s ical   g en et ic   alg o r ith m   ( C G A )   [ 3 8 ] ,   r an d o m   o f f s p r in g   g en er atio n   g e n etic  alg o r it h m   ( R OGG A )   [ 3 6 ]   an d   cr o w d i n g   alg o r ith m   [ 3 7 ] .   T h co m p ar ativ r es u lts   lead   to   co n clu s i o n   th at  t h p r o p o s ed   G I GA   o u tp er f o r m ed   t h ese s   alg o r ith m s .   T h r est  o f   th p ap er   is   o r g an ized   as  f o llo w s Sectio n   2   r ev ie w s   th r elate d   r esear c h es  o n   GI   p r o b lem .   Sectio n   3   p r esen t s   t h C FG  in d u ctio n   ap p r o ac h   u s i n g   G A   ad ap ted   in   t h i s   p ap er .   T h is   s ec tio n   s h o w s   th c h r o m o s o m s tr u c t u r in g ,   f it n es s   f u n ctio n   a n d   r ep r o d u ctio n   o p er ato r s   th at   h a v b ee n   e m p lo y ed   f o r   C F G   in d u ctio n .   Sect io n   4   s h o w s   th p u s h   d o w n   a u to m ata  s i m u la to r   w it h   t h v ar io u s   m et h o d s   i n co r p o r ated   f o r   th e   v er if ica tio n   p u r p o s e.   T h ex p er im e n tal  s et u p ,   r esu lt s   an d   d is cu s s i o n   o n   r esu lt s   ar g iv en   i n   Sectio n   5 .     Sectio n   6   co n clu d e s   th p ap er   an d   ass es s es t h f u t u r p er s p ec tiv es.       2.   RE L AT E WO RK   Go ld   [ 1 8 ]   p r o p o s ed   th f ir s l ea r n in g   m o d el  to   ad d r ess   I s   th in fo r ma tio n   s u fficien to   d etermin e   w h ich   o th p o s s ib le   la n g u a g es  is   th e   u n kn o w n   la n g u a g e? ”,   b u it  w a s   s u f f er ed   b ec au s s u f f icie n in f o r m atio n   ab o u t h id en ti f i ca tio n   o f   co r r ec g r a m m ar   d o es  n o e x is t.  T o   ad d r ess   th is s u o f   [ 1 8 ] ,   An g lu i n   [ 1 9 ]   p r o p o s ed   tell  tales.  A lt h o u g h ,   Go ld   [ 1 8 ]   laid   th e   f o u n d atio n   o f   lear n i n g   m o d el ,   b u B u n k a n d   A lb er to   [ 2 0 ]   p r o p o s ed   t h f ir s u s ab le  lear n in g   m o d el   also   s u f f er ed   s in ce   it  w a s   u n ab le  to   d ea w it h   n eg ati v d ata,   w as   n o f it  f o r   n o is y   d ata,   d o es  n o s u itab le  f o r   f i n ite  s ta te  m ac h in e,   t h er ef o r g o o d   f o r m al  la n g u a g th eo r y   w a s   lo s t.  T e ac h er   an d   q u er y   lear n in g   m o d el,   al s o   r ef er r ed   as   an   o r ac le  w a s   p r o p o s ed   in   [ 2 1 ]   is   s u p er v i s ed   lear n in g   m o d el  i n   w h ich   a n   o r ac le  k n o w s   th a n s w er .   I w as   f o u n d   ca p ab le  in   an s w er i n g   a   p ar ticu lar   t y p o f   q u er y   u s i n g   a n   i n f er e n ce   s y s te m ,   b u i m p le m e n ti n g   a n   o r ac le  is   m at ter   o f   co n ce r n ,   w h ic h   n ee d s   v as t   in f o r m atio n ,   h en ce   le s s   co m m o n l y   u s ed ,   w h er ea s   Go ld s   m o d el  is   m o r p o p u lar .   Valian [ 2 2 ]   co m b i n ed   th b est  f ea t u r es  o f   [ 1 8 ]   an d   [ 2 1 ]   an d   p r esen ted   p r o b a b ly   ap p r o x i m atel y   co r r ec t ( P A C )   lear n i n g   m o d el.   T h P A C   lear n i n g   m o d el  s u f f er ed   d u to   th f o llo w i n g   r ea s o n s :   T y p e   3 R e g u l a r   L a n g u a g e T y p e   2 C o n t e x t   F r e e   L a n g u a g e C o n t e x t   S e n s i t i v e   L a n g u a g e T y p e   1 T y p e   0 U n r e s t r i c t e d   L a n g u a g e F i n i t e   A u t o m a t a P u s h d o w n   A u t o m a t a L i n e a r   B o u n d e d   A u t o m a t a T u r i n g   M a c h i n e Languages A u t o m a t a Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  6 ,   No .   3 ,     Sep tem b er   2 0 1 7   :   10 0     11 1   102   1)   P A C   lear n i n g   ass u m es   th a t h in f er en ce   al g o r it h m   m u s le ar n   in   p o l y n o m ial  ti m u n d er   all  d is tr ib u tio n ,   b u t th i s   b eliev e s   is   to o   s tr in g   i n   r ea lit y .   2)   P A C   lear n in g   is   n o f it  f o r   n e g ati v an d   NP   h ar d   eq u i v alen ce   r esu lts .   A   m o d i f ied   v er s io n   o f   P A C   m o d el   w a s   p r esen t i n   [ 2 3 ]   in   w h ic h   s i m p licit y   w as  m ea s u r ed   u s i n g   Ko l m o g o r o v   co m p le x it y .   I n d u cti v in f er en ce   i s   th p r o ce s s   o f   m ak i n g   g e n er aliza tio n   f r o m   th i n p u t.  W y ar d   [ 2 4 ]   s h o w ed   th e   i m p ac o f   d if f er en g r a m m a r   r ep r esen tatio n .   T h ex p er im en tal  r esu l ts   p r esen ted   t h a th ev o l u tio n ar y   alg o r ith m   ( E A )   u s i n g   s ta n d ar d   co n te x f r ee   g r a m m ar   ( C FG)   ( B ac k u s   Nau r   Fo r m   ( B NF) )   o u tp er f o r m ed   o t h er s   [ 2 4 ] .   T h an ar u k   an d   Ok u m ar u   [ 2 5 ]   class if ied   GI   in to   th r ee   ca teg o r ies:   s u p er v i s ed ,   s em i - s u p er v i s ed   an d   u n s u p er v is ed .   J av ed   et.   al  [ 2 6 ]   p r o p o s ed   g en etic  p r o g r am m in g   ( GP )   b ased   ap p r o ac h   to   lear n   th C FG.   T h w o r k   p r esen ted   in   [ 2 6 ]   w a s   th e   ex te n s io n   o f   th w o r k   d o n i n   [ 2 4 ] .   A   s eq u e n tial  s tr u ct u r in g   ap p r o ac h   w a s   p r o p o s ed   in   [ 2 8 ]   th at  p e r f o r m   co d in g   an d   d ec o d in g   o f   b in ar y   co d ed   ch r o m o s o m es   in to   ter m in al s   an d   n o n - ter m in al s   a n d   v ice - v er s a.   G A   b ased   C F i n d u ctio n   l i b r ar y   w a s   p r o p o s ed   in   [ 2 8 ,   2 9 ] .   ca s s t u d y   o n   GI   w a s   p r o p o s ed   in   [ 2 7 ]   in cl u d es  t h b asic s   o f   G in   w h i ch   s i m p le   cr o s s o v er   ( o n e   an d   t w o   p o in ts )   a n d   b it   in v er s io n   m u tat io n   o p e r ato r s   w er u ti lized .   Hr n cic  et  al  [ 3 1 ,   3 2 ]   im p le m en ted   m e m etic  alg o r ith m   ( M A )   f o r   GI ,   w h ic h   as s is d o m ai n   ex p er ts   an d   s o f t w ar lan g u ag e n g i n ee r s   to   d ev elo p   d o m ai n - s p ec if ic  la n g u a g es   (D SLs)  b y   au to m atica ll y   p r o d u cin g   g r a m m ar .   T h eo r is ts   an d   e m p ir icis ts   ar t h t w o   m ai n   g r o u p s   co n tr ib u ti n g   i n   GI   [ 3 3 ,   3 4 ] .   L an g u a g class es  a n d   lear n in g   m o d els   w er co n s id er ed   b y   th e   t h eo r is ts   g r o u p ,   w h er ea s   e m p ir ici s ts   g r o u p   d ea lt  w it h   p r ac tical   p r o b lem s .   A   d etailed   s u r v e y   o f   v ar io u s   GI   alg o r it h m s   h as b ee n   p r esen ted   in   [ 4 ] ,   [ 3 3 ,   3 5 ] .       3.   G RAM M AT I CAL I NF E RE NCE US I N G   G E N E T I A L G O RI T H M   I n   t h is   s ec tio n ,   t h a u th o r   h a s   p r esen ted   a   b lo ck   d ia g r a m ,   s h o w s   t h p r o ce s s   o f   t h GI   u s e s   G A.   T h er ex is ts   d if f er e n GI   ap p r o ac h es  w er p r o p o s ed   a s   d is c u s s ed   in   Sectio n   2 .   T h au th o r s   h a v i m p le m e n ted   GA   b ased   ap p r o ac h   f o r   C FG   in d u ctio n .   Fig u r 2   d ep icts   th b lo ck   d iag r a m   f o r   C FG in d u ctio n   u s es a   G A .           Fig u r 2 .   B lo ck   d iag r a m   f o r   c o n tex f r ee   g r a m m ar   in d u ct io n   u s i n g   G A .       T h o v er all  p r o ce s s   h a s   b ee n   d iv id ed   in to   t w o   d if f er e n t   p h ase.   T h P h ase - 1   is   r esp o n s ib le  f o r   p r o d u ctio n   r u le  g e n er atio n   a n d   v er if icatio n   o v er   P DA   s i m u lato r ,   w h er ea s   P h a s e - 2   s h o w s   th s tep s   o f   G in co r p o r ated   to   o p tim ize  t h s ea r ch   p r o ce s s   an d   ex p lo r th s ea r ch   s p ac ad eq u atel y.   T h GI   p r o ce s s   s tar ts   g e n er ati n g   t h in itial  r an d o m   b i n ar y   c h r o m o s o m ( B C ) ,   w h ich   i s   th en   m ap p ed   to   ap p r o p r iate  s y m b o lic  c h r o m o s o m e   ( S C )   r ep r esen tat io n   o f   ter m i n als   a n d   n o n - ter m i n als  i n   a   s eq u en t ial   m an n er .   T h SC   h as  b ee n   d i v id ed   in to   eq u al  b lo ck   s ize  o f   f iv eq u al  to   p r o d u ctio n   r u le  le n g t h .   E ac h   SC   h as   b ee n   tr ac ed   f r o m   t h s tar s y m b o S   to   ter m i n al  to   r e m o v u s les s   p r o d u ctio n   a n d   r est  o f   t h p r o d u ctio n s   h av b ee n   test ed   f o r   r e m o v al  o f   lef r ec u r s io n ,   u n i p r o d u ctio n ,   a m b ig u it y   a n d   lef f ac to r .   A   s tr i n g   to   b test ed   h as  b ee n   s elec ted   a n d   p ass ed   f o r   th v alid it y ,   i.e .   ac ce p tab ilit y   o f   t h C FG  eq u iv ale n t o   th ch r o m o s o m e.   T r a i n i n g   d a t a ( P o s i t i v e   a n d   n e g a t i v e ) G e n e r a t e   r a n d o m   c h r o m o s o m e P e r f o r m   s e q u e n t i a l   m a p p i n g   o f   b i n a r y   c h r o m o s o m e   t o   s y b o l i c   r e p r e s e n t a t i o n S p l i t   t h e   s y b o l i c   r e p r e s e n t a t i o n T r a c e   t h e   r u l e   f r o m   s t a r t   s y m b o l   t o   r e p r e s e n t   t h e   s p l i t e d   s y b o l i c   r e p r e s e n t a t i o n   i n   B N F   f o r m V e r f i y   t h e   i n p u t   s t r i n g   o v e r   t h e   r u l e s   i n d u c e d   t h r o u g h   P D A   S i m u l a t o r E v a l u a t e   t h e   f i t n e s s S e l e c t i o n   o f   p a r e n t   p a i r s A p p l y   r e p r o d u c t i o n   o p e r a t i o n s R e p l a c e m e n t   t o   i n c o r p o r a t e   n e w   p o p u l a t i o n C h e c k   t h e   t e r m i n a t i o n   c o n d i t i o n D i s p l a y   t h e   f i n a l   C F G   w i t h   t h e   t i m e   c o n s u m e d P h a s e - I P h a s e - I I S t a r t S t o p Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       Gen etic  A lg o r ith fo r   Gra mm a r   I n d u ctio n   a n d   R u les V erif ica tio n   th r o u g h   a ...   ( Ha r i Mo h a n   P a n d ey )   103   T h test   s tr in g   a n d   th C FG  r u les  ar t h in p u to   th f i n ite   s tate  co n tr o ller ,   w h ic h   v er if i es  th ac ce p tab ilit y   th r o u g h   t h p r o li f er atio n   o n   t h P DA .     3 . 1 .     Chro m o s o m Str uct ure     r an d o m   in i tial  b i n ar y   ch r o m o s o m e s   ( B C )   co n s i s o f   s eq u en ce   o f   0 s   an d   1 s   h a v b e en   cr ea ted   ( s ee   Fi g u r 4 ) .   T h B C   is   m ap p ed   in to   ter m in al s   a n d   n o n - ter m i n als   in   s eq u en tial  m a n n er   f o llo w i n g   3 - b it/4 - b it  c o d in g   t h at  d ep en d   o n   t h n u m b er   o f   s y m b o ls   p r ese n i n   th la n g u a g e.   I f   m o r th a n   t wo   s y m b o l s   ar u s ed   in   t h e   lan g u ag e   t h en   4 - b it   r ep r esen tatio n   h as   b ee n   u s ed   o th er w i s u s 3 - b it  r ep r ese n tatio n .   T h s tar s y m b o l   S   h a s   b ee n   m ap p ed   at  0 0 0 ”  an d   ?   r ep r esen ts   th n u l s y m b o m ap p ed   at  0 1 0 ”,   w h er ea s   f o r   o th er s   s y m b o ls   ( ter m i n al s   an d   n o n - te r m in a ls )   ar u s ed   as a p p r o p r ia te.       B in ar y   ch r o m o s o m e:   0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0     C o d in g   o f   ter m i n al  a n d   n o n - te r m in a ls   No n - ter m i n als   T er m in al s     000   1 100   A 001   0 101   B 111   ? 010   C 011   ? 110     S y m b o lic  ch r o m o s o m r ep r esen tatio n : S1 ? S?? S0 A B S0 S?? S ? C 0 C A S C AA ? 0 ? A 1 S1 ?? ? SA 0 0 ?     T h SC s   ar e   d iv id ed   i n to   b lo ck   s ize  o f   f iv e   eq u al   to   t h p r o d u ctio n   r u le  le n g t h   as   s h o w n   i n   T ab le  2 ,   w h ic h   ar t h e n   tr ac ed   f r o m   S‟   to   r e m o v t h i n s u f f icie n c y   p r ese n ts .   T h P D A   s i m u lat o r   ac ce p ts   test   s tr i n g   an d   th e   p r o d u ctio n   r u les  a s   a n   i n p u f o r   a n y   s p ec if ic  la n g u ag e,   v er i f ie s   t h ac ce p tab ilit y   v ia  p r o lif er atio n   o n   th P DA .     3. 2   F i t nes s   F un ct io n   T h f itn es s   o f   an   i n d iv id u al  h a s   b ee n   ca lcu lated   in   ea c h   G A   r u n   a n d   th e n   s elec tio n   o f   p ar en s tr in g   i s   d o n e.   I n   GI   p r o b le m ,   t h f i tn es s   o f   an   i n d iv id u al  c h r o m o s o m e   lar g el y   d ep en d s   u p o n   t h ac ce p tan c e   ( r ej ec tio n )   o f   th p o s itiv an d   n eg at iv s a m p le  s tr i n g s .   T h f itn es s   v al u in cr ea s f o r   ac ce p tin g   p o s iti v ( A P )   an d   r ej ec tin g   n eg at iv ( R N)   s a m p le,   w h er ea s   it  d ec r ea s es  f o r   ac ce p tin g   n e g ati v ( A N)   a n d   r ej ec tin g   p o s iti v e   ( R P )   s am p le.   T h p r o b lem   s p e cif ic  f ac to r   ( s )   also   p lay s   s ig n i f ican r o le  in   G A s   p er f o r m a n ce .   I n   ca s o f   GI ,   p r o d u ctio n   r u le  len g t h   ( P R )   is   an   i m p o r tan t f ac to r ,   h a s   b ee n   co n s id er ed   in   th f it n es s   ca lc u latio n .   E q u atio n   ( 1 )   h as b ee n   ap p lied   to   ca lcu late  t h f i tn e s s   o f   a n   in d i v id u a l.     * ( ( ) ( ) ) ( 2 * ) F i t n e s s C A P R N A N R P C P R         ( 1 )     T h f o llo w i n g   co n v e n tio n   h as  b ee n   f o llo w ed   f o r   th e   s elec tio n   o f   t h b est  g r a m m ar   r u les:   “A   g r a m m ar   t h at  ac ce p t s   all  t h p o s iti v s tr i n g s   a n d   r ej ec ts   th e n tire   n eg ati v s tr in g   f r o m   s et  o f   tr ain i n g   d at a   w it h   m in i m u m   n u m b er   o f   p r o d u ctio n   r u le s .   T h v a lu o f   co n s ta n ( C =   1 0 )   is   f o u n d   s u f f icie n to   ac co m m o d ate  g r a m m ar   r u les  b lo ck s   p r esen t i n   th s y m b o lic   ch r o m o s o m e.       3. 3 .     Repro du ct io n O pera t o r s   T h GA‟ s   p er f o r m a n ce   lar g e l y   d ep en d s   o n   t h t w o   m o s t   co m m o n l y   u s ed   g en etic  o p e r ato r s   ar e   cr o s s o v er   an d   m u tatio n .   T h o p er ato r s   cr o s s o v er   an d   m u tatio n   p la y   s i g n i f ican r o l in   th p o p u lat io n   d iv er s it y   m a n a g e m e n t a n d   th e r ef o r i m p r o v es t h co n v er g en ce   s p ee d .   A   v ar iatio n   o f   t w o   p o in cr o s s o v er   b ased   o n   th c y clic  cr o s s o v er   h as  b ee n   i n co r p o r ated   to   p er f o r m   th cr o s s o v er   o p er atio n .   T h in v er ted   m u ta tio n   m et h o d   h as  b ee n   ap p lied   w it h   r an d o m   m a s k .   A s   w k n o w   th e   m u tatio n   o p er ato r   in tr o d u ce s   d iv er s it y   i n   th e   p o p u latio n   h e l p s   to   k ee p   t h s ea r c h   p r o ce s s   aliv e.   R a n d o m   m as k   is   u s e f u in   ac h iev i n g   th d iv er s it y .   T h f o llo w i n g   co n v e n tio n   h as  b ee n   ap p lied s i m p ly   ap p l y   XO R   o p er atio n   b et w ee n   t h p ar e n s tr in g s   r ec eiv ed   a f ter   cr o s s o v er   o p er a tio n   a n d   t h r an d o m   o f f s p r in g ”.   An   ex a m p le  f o r   b o th   cr o s s o v er   an d   m u ta tio n   o p er atio n s   h av b ee n   r ep r esen ted   in   Fi g u r 3 .             Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  6 ,   No .   3 ,     Sep tem b er   2 0 1 7   :   10 0     11 1   104   .         P1   1   1   0   1   0   0   1   1     P 11   P 12   P 13   P2   0   0   1   0   1   1   1   0     P 21   P 22     P 23           OS1   1   0   1   0   1   1   1   1     P 22   P 13   P 11   OS2   0   1   0   1   1   0   0   0     P 12   P 23   P 21   ( a)   OS1   1   0   1   0   1   1   1   1                     RM   1   0   1   0   1   0   1   0     OS1  =   OS1  XO R   R M   OS1   0   0   0   0   0   1   0   1   ( b )     Fig u r 3 .   D e m o n s tr atio n s   o f   c r o s s o v er   an d   m u tatio n   o p er atio n s .   ( a)   R ep r esen ti n g   th t w o   p o in t c u t c r o s s o v er   b ased   o n   cy c lic  cr o s s o v er .   ( b )   I n v er ted   m u tatio n   b y   g e n er ati n g   r a n d o m   m a s k   ( R M)   an d   th en   ap p l y in g   XO R   o p er atio n .       3. 3 .     Ver if ica t io n o f   Rules   us ing   P DA  Si m u la t o r   T h is   s ec tio n   e x p lain s   t h wo r k in g   o f   p u s h d o w n   a u to m a ta  in co r p o r ated   d u r in g   C FG   in d u ctio n .   T h P DA   s i m u lato r   u tili ze s   v ar io u s   m et h o d s   f o r   th v er i f i ca tio n   p u r p o s e.   T h d escr ip tio n   o f   ea ch   m et h o d   u s ed   in   t h i m p le m en tat io n   o f   P DA   s i m u lato r   is   o u tli n ed   b e lo w :   P DA _ S imu la to r   ( in p u t_ S tr in g ,   S ta ck ) :   I ac ce p ts   in p u t   s tr i n g   a n d   s tac k   a s   an   i n p u t.  T h p u r p o s o f   t h i s   p r o ce d u r is   to   s i m u late  t h e   o v er all  w o r k in g .   I u s es  to p   o f   s tack   ( T OS)   f o r   th s i m u latio n   p u r p o s e.   I f   T OS  i n p u s y m b o $ ,   i n d icate   th at   t h i n p u t   s tr i n g   i s   a cc ep ted   f o r   th e   g r a m m ar .   I f   T OS  T er m i n al  a n d   th f ir s s y m b o m atc h es  w i th   th s y m b o p r ese n at  T OS,  th en   b o th   th s y m b o ls   ar r e m o v ed .   I f   T OS  n o n - ter m i n al  ( X) ,   t h e n   i n   s u c h   s it u atio n ,   all  t h p r o d u ctio n   o f   X   r ep lace   t h T OS  w i th   t h e   r ig h s id o f   t h p r o d u ctio n   r u le  an d   ca ll  t h P DA _ S imu la to r ( )   r ec u r s iv el y .   I n   ca s o f   n o n - ac ce p tan ce ,   t h s elec ted   p r o d u ctio n   r u les r ep ea t th p r o ce s s   f o r   an o th er   p r o d u ctio n   th at  s tar t s   w it h   X .   g et_ in p u t ( T_ in p u t _ S tr in g ) :   I s i m p l y   r etu r n s   t h n e x t te r m i n al  p r esen t in   t h i n p u t s tr in g .   g et_ To p _ S   ( T_ S ta ck ) :   R etu r n s   T OS sy m b o l p r esen t i n   th s t ac k .   r emo ve _ fir s t_ in p u t ( ) :   I t is u s e d   to   r em o v t h f ir s t s y m b o l o f   th i n p u t stri n g .   r emo ve _ TOP_ S ta ck   ( ) :   I t is u s ed   to   r em o v T OS ite m   f r o m   t h s tac k .   co p y_ r ig h t   ( T_ S ta ck ,   X ) :   I ac ce p s tack   an d   p r o d u ctio n   r u les  as  an   in p u t.  I is   u s ed   to   r ep lace   th T OS  w it h   r ig h s id o f   th p r o d u ctio n   r u l e.   ve r ify_ s tr in g   ( S tr in g   s tr ) :   T h is   p r o ce d u r is   ex ec u ted   to   tak e   th d ec is io n   ab o u th ac ce p tan ce   o r   r e j ec tio n   o f   th in p u t stri n g   “str”   T h p r o ce d u r P DA _ S imu la t o r   ( in p u t_ S tr in g ,   S ta ck )   an d   its   as s o ciate d   f u n ctio n s   d e f i n itio n s   ar g iv e n   b elo w :   P r o ce d ur e:   P DA _ Sim ula to r   ( inp ut_ Str i ng ,   Sta ck )   B eg in     Set T _ in p u t_ Strin g   i n p u t_ S tr in g     Set T _ Stack   Stack     Set X   g et_ in p u t( )     Set S  g et_ T o p _ S( )     I f   s tack   o v er f lo w ( )   th e n     r etu r n   ( 2 )     E n d   I f     I f   ( E n d _ o f _ Strin g   & &   E n d _ o f _ Stac k )   th e n     r etu r n   ( 1 )     E n d   I f     I f ( S = T er m in a l & &   S)     p er f o r m   r e m o v e_ f ir s t_ in p u t ( )     p er f o r m   r e m o v e_ T OP _ Stack   ( )     E n d   I f     I f ( S =   n o n - ter m in al)   t h en     Fo r   all  p r o d u ctio n   r u les i n   P   s tar tin g   w it h   S     I f   p r o d u ctio n   r u le  is   N u ll t h en     p er f o r m   r e m o v e_ T OP _ Stack   ( )   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       Gen etic  A lg o r ith fo r   Gra mm a r   I n d u ctio n   a n d   R u les V erif ica tio n   th r o u g h   a ...   ( Ha r i Mo h a n   P a n d ey )   105     E ls e     p er f o r m   r e m o v e_ T OP _ Stack   ( )     p er f o r m   co p y _ r ig h t ( S,  x )     E n d   Fo r     E n d   I f     Set Fo u n d   P DA _ Si m u la to r   ( T em p _ Strin g ,   T em p _ S tack )     I f   ( Fo u n d   =1 )   T h en     r etu r n   1     E ls     r etu r n   0     E n d   I f   E n d     P r o ce d ur e:   g et_ inp ut ( T _ inp ut_ Str i ng )   B eg in     r etu r n   f ir s t s y m b o f r o m   T _ in p u t_ Strin g   E n d   P r o ce d ur e:   g et_ T o p _ S ( T _ Sta ck )   B eg in     r etu r n   f ir s t s y m b o f r o m   t h T _ Stack   E n d   P r o c ed ur e:   r em o ve _ f ir s t_ inp ut()   B eg in     d elete   f ir s t s y m b o f r o m   t h T _ in p u t_ Stri n g   E n d   P r o ce d ur e:   r em o ve _ T OP _ Sta ck   ( )   B eg in     d elete   f ir s t s y m b o f r o m   t h T _ Stack   E n d   P r o ce d ur e:   co p y_ r ig ht(T _ Sta ck ,   X )   B eg in     C o p ies th R HS o f   t h p r o d u ctio n   to   T _ Sta ck   E n d   P r o ce d ur e:   ve r if y_ s tr i ng ( Str i ng   s tr )   B eg in     ST S$     STT   a p p en d   $ ”  to   s tr     R es u lt =   P DA _ Si m u lato r   ( s tr ,   ST K)     R es u lt ( ? )     C ase  0 :     Msg   R ej ec ted ”;     C ase  1     Msg   A cc ep ted     C ase  2 :       Msg   Stac k   o v er f lo w   E n d     C o m p u tatio n a l   s i m u latio n   r es u lts   h a v b ee n   s h o w n   f o r   b o th   t h ca s e,   i.e .   f o r   th e   ac ce p tan ce   a n d   r ej ec tio n   o f   th i n p u s tr i n g .   T h s imu la tio n   r esu lt - 1   r ep r esen th e   ac ce p tan ce   o f   th in p u s tr i n g   ( ) ( ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) ) ”  in   T ab le  1 .   T h b est  p o s s ib le  C FG  u s ed   f o r   th i s   p u r p o s is   <{ S,  M} ,   {( , ) },   {S M M ( S)  M} ,   S>.                   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  6 ,   No .   3 ,     Sep tem b er   2 0 1 7   :   10 0     11 1   106     T ab le  1 .   P DA   s i m u latio n   r es u l t - 1   f o r   lan g u ag b ala n ce d   p ar en th e s is ”  f o r   th te s t stri n g   ( ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) )   BC   0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 1 1 0 0 1 0 0   SC   C   )   B   )   ?   ) )   A   C   A   S   A   S   S ?   S   S   ( S )   S ?   C   A   ?   S ? ?   ?   ?   S   A   A   ?   ?   ( A   C   ( ( C )   B ) ? )   )   A   C   A   S   A   S   S   ?   S   S   ( S )   S   C   A ? ?   S ? ?   ?   ?   S   A   A ? ?   (   A   C   (   (   S p l i t t i n g   o f   S C   C ) B ) ?   ) ) A C A   S A S S ?   S S ( S )   S ? C A ?   S ? ? ? ?   S A A ? ?   ( A C ( (   C ) B ) ?   ) ) A C A   S A S S ?   S S ( S )   S C A ? ?   S ? ? ? ?   S A A ? ?   ( A C ( (   R e mo v a l   o f   u n w a n t e d   r u l e s   C ) B ) ?   ) ) A C A   S A S S ?   S S ( S )   S C A ? ?   S ? ? ? ?   S A A ? ?   ( A C ( (   R u l e   a d d e d   a r e :   S ? ? ? ?   S S ( S )   R u l e   a f t e r   u se l e ss re mo v a l   f r o m t e r mi n a l   si d e :   S ? ? ? ?   S S ( S )   R e mo v a l   o f   u n w a n t e d   r u l e s o v e r   n   n u mb e r   o f   r u l e s a d d e d   a r e   :   2   O r i g i n a l   r u l e s a r e   : : 8   R u l e   a f t e r   u se l e ss re mo v a l   f r o m S si d e :   S ? ? ? ?   S S ( S )   T e st   f o r   r e c u r si o n   a t :   S ? ? ? ?   S S ( S )   SC   M   (   S   )   M   M   (   S   )   M   S   ?   ?   M   ?   ?   M   ?   ?   ?   ?   ?   S   ?   M   ?   ?   ?   M   ?   ?   ?   ?   ?   S   M   ?   ?   ?   ?   M   ?   ?   ?   ?   ?   F i n a l   r u l e s i n d u c e d   a r e :   S M   M ?   M ( S ) M   P D A   S i mu l a t o r   p r o l i f e r a t i o n   f o r   v e r i f i c a t i o n   o f   s t r i n g :   ( ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) )   S T R I N G   I S   ( ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M$   S T R I N G   I S   ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M ) M $   S T R I N G   I S   ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M ) M ) M $   S T R I N G   I S   ( ) ) ( ) ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M ) M ) M $   S T R I N G   I S   ( ) ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M ) M $   S T R I N G   I S   ( ) ) ( ( ( ) ) ) $   S t a c k   i s   M ) M $   S T R I N G   I S   ((()))$   S t a c k   i s   M$   S T R I N G   I S   (()))$   S t a c k   i s   M ) M $   S T R I N G   I S   ()))$   S t a c k   i s   M ) M ) M $   ( ( ( ) ( ) ) ( ) ( ) ) ( ( ( ) ) )   st r i n g   i s a c c e p t e d       T h ese  g r a m m ar s   h a v b ee n   in d u ce d   f r o m   t h tr ain i n g   d ata   em p lo y in g   GA   i n   Fi g u r 2 .   I ca n   b e   s ee n   t h at  th i n p u s tr i n g   an d   p r o d u ctio n   r u les  ar th in p u t   f o r   th f i n ite  s tate  co n tr o ller ,   w h ich   v er if ie s   th e   s tr in g   an d   p r o d u ctio n   r u le s   th r o u g h   p r o li f er atio n   v ia  th P D A   s i m u lato r .       4.   RE SU L T A ND  AN AL Y SI S   T h co m p u tatio n al  e x p er i m e n ts   h a v b ee n   co n d u cted .   N et  B ea n s   I DE   7 . 0 . 1 ,   I n tel  C o r T 2   p r o ce s s o r   ( 2 . 8   GHz )   w it h   2   GB   R A h a s   b ee n   u s ed .   Fo u r   d if f er e n t y p e s   o f   la n g u a g e s   o f   v ar y in g   p atter n s   h av b ee n   ta k e n ,   ar g i v en   i n   T ab le  2 .       T ab le  2 .   T est L an g u a g es  De s c r ip tio n   L - id   D e scri p t i o n s   S t a n d a r d   S e t   L1   ( 1 0 ) *   o v e r   ( 0   +   1 ) *   T o mi t a   / D u p o n t   S e t     L2   A l l   st r i n g   n o t   c o n t a i n i n g   0 0 0   o v e r   ( 0 + 1 ) *   T o mi t a   / D u p o n t   S e t   L3   B a l a n c e d   P a r e n t h e se s   H u i j se n   / K e l l e r   &   L u t z   se t     L4   O d d   b i n a r y   n u m b e r   e n d i n g   w i t h   1   D u p o n t   se t         4 . 1 .     P a ra m et er s   Select io n a nd   T u nin g   T h o r th o g o n al  ar r a y   m et h o d   h as  b ee n   u s ed   f o r   t h p ar a m et er   s elec tio n .   Or t h o g o n a ar r a y   is   h e lp f u l   in   s etti n g   t h w ell  b ala n ce d   e x p er im e n t s   a n d   T ag u c h s i g n a l - to - n o i s r atio s   ( SN R ) ,   w h ich   a r lo g   f u n ct io n s   o f   th d es ir ed   o u tp u t,  s er v as a n   o b j ec tiv f u n ctio n   f o r   o p ti m iz atio n   t h at  h elp s   i n   d ata  a n al y s i s   an d   p r ed ictio n   o f   o p tim u m   r es u lts .   E q u at io n   ( 2 )   h as b ee n   u s ed   to   ev al u ate  SN R .     2 1 1 0 l o g u N u i u i y S N R N                     ( 2 )     W h er e,   i ex p er im e n n u m b er ,   u tr ial  n u m b er ,   i N n u m b er   o f   tr ials   f o r   th e x p er i m e n t,  an d   u y n u m b er   g e n er atio n s   ta k e n   in   ea ch   tr ials   to   r ea ch   to   th s o l u tio n .         Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       Gen etic  A lg o r ith fo r   Gra mm a r   I n d u ctio n   a n d   R u les V erif ica tio n   th r o u g h   a ...   ( Ha r i Mo h a n   P a n d ey )   107   T ab le  3 .   P ar am eter   s elec tio n   b y   o r th o g o n a l a r r a y   m et h o d   Ex .   N o .   PS   P R L   CS   CR   MR   M e a n s   C o f f .   V a r i a t i o n   S t d . d e v .   S N R   1   1 2 0   5   1 2 0   0 . 6   0 . 5   3 . 5 6 6 6 7   0 . 0 4 2 8 2 7 8   0 . 1 5 2 7 5 3   - 1 1 . 0 5 0 6   2   1 2 0   5   1 2 0   0 . 9   0 . 8   4 . 0 6 6 6 7   0 . 0 3 7 5 6 2 1   0 . 1 5 2 7 5 3   - 1 2 . 1 8 8 9   3   1 2 0   8   2 4 0   0 . 6   0 . 5   3 . 2 6 6 6 7   0 . 0 4 6 7 6 1 0   0 . 1 5 2 7 5 3   - 1 0 . 2 8 8 4   4   1 2 0   8   24 0   0 . 9   0 . 8   3 . 5 6 6 6 7   0 . 0 9 0 1 2 7 6   0 . 3 2 1 4 5 5   - 1 1 . 0 6 8 7   5   3 6 0   5   2 4 0   0 . 6   0 . 8   3 . 5 0 0 0 0   0 . 0 2 8 5 7 1 4   0 . 1 0 0 0 0 0   - 1 0 . 8 8 3 7   6   3 6 0   5   2 4 0   0 . 9   0 . 5   3 . 5 9 0 0 0   0 . 0 4 6 0 2 4 3   0 . 1 6 5 2 2 7   - 1 1 . 1 0 8 0   7   3 6 0   8   1 2 0   0 . 6   0 . 8   3 . 3 0 0 0 0   0 . 0 6 0 6 0 6 1   0 . 2 0 0 0 0 0   - 1 0 . 3 8 0 9   8   3 6 0   8   1 2 0   0 . 9   0 . 5   3 . 5 0 0 0 0   0 . 0 4 9 4 8 7 2   0 . 1 7 3 2 0 5   - 1 0 . 8 8 8 4   R e sp o n se   f o r   S N R   ( S mal l   i s b e t t e r )   L o w   - 1 1 . 1 5   - 1 1 . 3 1   - 1 1 . 1 3   - 1 0 . 6 5   - 1 0 . 8 3   F o r   ( P S : P R L : C S : C R : M R =   1 2 0 :   5 :   1 2 0 :   0 . 6 :   0 . 5 )   H i g h   - 1 0 . 8 2   - 1 0 . 6 6   - 1 0 . 8 4   - 1 1 . 3 1   - 1 1 . 1 3   F o r   ( P S : P R L : C S : C R : M R =   3 6 0 :   8 :   2 4 0 :   0 . 9 :   0 . 8 )   D e l t a   0 . 3 3   0 . 6 5   0 . 2 9   0 . 6 6   0 . 3 0   D e l t a :   d i f f e r e n c e   b e t w e e n   L o w :   H i g h   R a n k   3   2   5   1   4   R a n k :   b a se d   o n   d e l t a   ( 1 :   H i g h e st   a n d   5 :   L o w e st )   S u i t a b l e   C o mb i n a t i o n   1 2 0   5   1 2 0   0 . 9   0 . 8   S N R   ( smal l e r   i s b e t t e r )   - 1 2 . 1 8 8 9   S N R :   S i g n a l   t o   n o i se   r a t i o       T h p er f o r m an ce   o f   t h G A   is   s ig n if ican t l y   a f f ec te d   b y   p o p u latio n   s ize  ( P S),   ch r o m o s o m s ize  ( C S),   cr o s s o v er   r ate  ( C R )   an d   m u ta tio n   r ate  ( MR).   T h p er f o r m a n ce   o f   G A   lar g el y   d ep en d s   o n   P S,  C S,  C R   an d   MR.  I n   GI ,   p r o d u ctio n   r u le  l en g t h   ( P R L )   is   al s o   an   i m p o r tan f ac to r   th at  a f f ec ts   th r es u lt.  T h o r th o g o n a l   ar r ay   i n v o l v es  f iv co n tr o f ac to r s   w it h   t w o   le v els:   P S =   [ 1 2 0 ,   3 6 0 ] ,   P R L =   [ 5 ,   8 ] ,   C S=   [ 1 2 0 ,   2 4 0 ] ,   CR=   [ 0 . 6 ,   0 . 9 ]   an d   MR =   [ 0 . 5 ,   0 . 8 ] ,   w h er f o llo w in g   s ett in g   g av t h b est  r esu l ts   P S=   1 2 0 ,   P R L =   5 ,   C S=   120,   CR=   0 . 9   a n d   MR=   0 . 8   ( See  T ab le  3   ex p er im e n n u m b er   2 ,   SNR = - 1 2 . 1 8 8 9 )   is   tak en   f o r   th r o b u s p r o ce s s   d esig n   an d   to   co n d u ct  t h ex p er i m en ts .     4 . 2   P er f o rm a nce  Co m pa ris o n   T h au th o r   h as  co m p ar ed   th p er f o r m a n ce   o f   t h p r o p o s ed   ap p r o ac h   w i th   C G A ,   R O GG A   [ 3 6 ]   an d   cr o w d in g   m et h o d   [ 3 7 ] .   T h s a m p ar a m e ter s   s e tti n g   h a v b e en   u s ed   f o r   C G A ,   R OGG A   a n d   cr o w d in g   i n   t h e   p r o p o s ed   GA .   T h C G w o r k s   u s i n g   r an d o m   i n it ial  p o p u latio n   o f   f i x ed   l en g t h   ch r o m o s o m e s .   I s tar ts   w it h   s et  o f   s o lu tio n   r ep r esen ted   b y   ch r o m o s o m e.   Usi n g   an   ap p r o p r iate  s elec tio n   tec h n iq u s o lu tio n   f r o m   o n e   p o p u latio n   is   p ick ed   d ep en d i n g   o n   it s   f it n es s   a n d   u s ed   to   f o r m   n e w   o f f s p r in g .   T h i s   p r o ce s s   r ep ea ted   u n ti l   th G A   r ea c h ed   to   th t h r es h o ld   o r   m a x i m u m   n u m b er   o f   g en er atio n .   Fo r   th p u r p o s o f   a n   ev o lu tio n   t h C G p er f o r m   o n eti m cr o s s o v er   an d   m u ta t io n   o p er ato r   f o r   r ep r o d u ctio n .   T h en   in d i v id u a ls   ar p ick ed   d ep en d i n g   o n   th eir   f itn e s s   v al u to   ac t a s   p ar en ts   to   g en er ate  o f f s p r in g   i n   th n e w   g en er atio n .     I n   R OGG A ,   b e f o r ap p l y i n g   r ep r o d u ctio n ,   test   f o r   s i m il ar it y   o f   t h g e n etic  m ater ial   h a s   b ee n   co n d u ct ed     if   f o u n d   s i m i la r ,   th en   g e n er ate  o f f s p r i n g     p r o d u cin g   r an d o m   s o l u ti o n   o th er w is ap p l y   r ep r o d u ctio n   in   n o r m al  f as h io n .     De  J o n g   ( 1 9 7 5 )   in tr o d u ce d   c r o w d in g   ap p r o ac h   to   p r eser v p o p u latio n   d iv er s it y   w h ic h   r esu lts   i n   p r ev en ti n g   p r e m at u r co n v er g en ce .   I t   w a s   ap p lied   in   th e   s u r v iv al   s o l u tio n   s tep   o f   t h G A   to   d ec id w h ic h   in d iv id u al  a m o n g   t h o s i n   t h cu r r e n p o p u latio n   an d   t h eir   o f f s p r i n g   in d i v id u al   w il p ass   to   t h n ex t   g en er atio n .   I t e li m i n ate s   th m o s t si m ilar   in d i v id u al  w h e n ev er   n e w   o n e n ter s   i n   s u b p o p u latio n .       4 . 3 .     Resul t s   a nd   Dis cu s s io n   T h ex p er im e n tal  r esu lts   s h o w   t h at  G A   is   ca p ab le  in   C FG  in d u ctio n .   T h m i n i m u m   d escr ip tio n   len g th   ( MD L )   p r in cip le   h a s   b ee n   ap p lied   an d   f o u n d   e f f e ctiv in   g e n er aliza tio n   a n d   s p ec ializatio n   o f   t h e   tr ain i n g   d ata.       T ab le  4 .   Gen er ated   g r am m ar   w it h   f it n es s   v al u an d   to tal  n u m b er   o f   r u les   L - id   F i t n e ss   G r a mm a r   V P S , , ,   L1   1 0 1 4   < {S },  { 0 ,   1 },   {S ? ,   S 1 0 S } ,   S >   L2   1 0 1 1   < {S , C , M } ,   { 0 ,   1 },   {S C C M ,   M ? ,   M 1 S M ,   C ? ,   C 0 },  S >   L3   1 0 1 4   < {S },  {( ,   ) } ,   {S ? ,   S   ( S ) S },  S >   L4   1 0 1 2   < {S ,   M },  { 0 ,   1 } ,   {S 1 M ,   S 0 S M ,   M S M ,   M ? },  S >               Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 2 5 2 - 8938   IJ - AI    Vo l.  6 ,   No .   3 ,     Sep tem b er   2 0 1 7   :   10 0     11 1   108   T ab le  5 .   C o m p ar is o n   b ased   o n   Gen er atio n   r an g e,   th r e s h o ld ,   t i m co n s u m ed ,   m ea n   ( µ)   an d   s tan d ar d   d ev iatio n   ( Std .   Dev iatio n )   f o r   ea ch   lan g u ag L 1   th r o u g h   L 4   A p p r o a c h   L - id   G e n .   R a n g e   T h r e sh o l d   T i me   ( i n   m i l l i se c o n d )   µ   S t d . D e v i a t i o n   G I G A   L1   5 ± 2   7   3 8 8 0 1 . 1   3 . 4   2 . 5   L2   2 2 ± 1 1   26   3 1 9 2 8 2 7   1 8 . 2   6 . 9   L3   8 ± 3   18   3 6 5 8 5 1 . 8   9 . 1   5 . 2 2   L4   9 ± 4   23   2 3 5 3 6 0 . 3   1 0 . 8   5 . 4 1   C G A   L1   6 ± 2   7   2 6 0 6 4 . 1   4 . 1   2 . 7 3   L2   1 4 ± 1 0   22   2 6 9 0 7 1 1   1 7 . 4   6 . 4 3   L3   8 ± 4   12   1 9 6 3 4 7   8 . 2   2 . 4 4   L4   7 ± 6   14   7 3 7 4 9 . 7   8 . 1   3 . 8 7   R O G G A   L1   4 ± 2   7   5 6 0 1 2 . 3   3 . 9   1 . 8   L2   2 0 ± 1 2   24   3 7 0 1 9 2 5   2 5 . 7   1 0 . 3 4   L3   7 ± 3   13   2 6 8 2 7 6 . 2   7 . 2   2 . 9 7   L4   1 2 ± 6   25   3 8 0 7 6 6 . 3   12   8 . 0 1   C r o w d i n g   L1   8 ± 6   32   3 5 9 0 7 7 . 3   8 . 7   2 . 7   L2   1 4 ± 1 2   27   3 6 8 8 2 0 3   1 4 . 3   7 . 8   L3   7 ± 6   24   2 5 8 7 2 3 . 1   9 . 8   2 . 5   L4   8 ± 6   15   8 0 0 7 8 . 5   9 . 2   1 . 6       T h tr ain in g   s et  an d   test   s et,   w h ic h   ar r eq u ir ed   f o r   th lear n in g   h a s   b ee n   g e n er ated   w ith   len g t h   L   ( L 0 ,   1 ,   2 ,   …. . )   s u ch   th at  it  co v er s   all  th p o s s ib le  v al id   s t r in g s   o f   th le n g th   L   till   t h s u f f icie n n u m b er   o f   v alid   s tr i n g s   o f   co r p u s   t h at  h as  b ee n   g e n er ated .   T h in v alid   s tr in g s   g e n er ated   d u r in g   th i s   p r o ce s s   ar co n s id er ed   as  n eg at iv e   s tr i n g s .   T h r es u lta n g r a m m ar s   ar v alid ated   ag a in s t h b e s k n o w n   a v ailab le  g r a m m ar .   T h s ta n d ar d   r ep r esen tat io n , , , V P S ha s   b ee n   ad ap ted   to   r ep r esen th g r a m m ar s   as  p r esen ted   in   T ab le  4 .   T h r esu lts   ar co llected   as  an   av er ag o f   t w e n t y   r u n s h e n ce   g en er at io n   r an g h a s   b ee n   u s ed   ( s ee   T ab le  5 ) .   T h P DA   s i m u lato r   an d   it s   as s o ciate d   m e th o d s   h a v b ee n   f o u n d   e f f ec ti v i n   v a lid ati n g   t h e   s tr in g s   u s in g   th e   r esu ltan g r am m ar   an d   i ts   eq u i v alen t   p r o lif er atio n   o n   t h s tack .   T h p r o lif er atio n   th r o u g h   P DA   s i m u lato r   p r ese n ted   i n   T ab le  1 ,   2 ,   an d   3   ar f o r   b es g r a m m ar s   r ec ei v ed   o v er   t wen t y   s u cc es s f u l   G r u n s .   T h au th o r   h as  f o llo w e d   in s ta n ta n eo u s   d escr ip to r   ( c u r r en s ta te,   cu r r en i n p u s tr i n g ,   s tack   co n te n t) ”  f o r   th p r o lif er atio n   p u r p o s e.   T h $   s y m b o i n d icate s   th en d   o f   t h i n p u a n d   b o tto m   o f   t h s tac k   r esp ec tiv el y .   T h au th o r   h as   s h o w n   b est   av er a g f it n es s   v s .   g e n er atio n   c h ar f o r   ea ch   la n g u a g L 1   t h r o u g h   L 4 ,   i n d icate s   t h at   th e   p r o p o s ed   GI GA  d o es  n o t   s h o w ed   an y   p r e m atu r e   co n v er g e n ce .   I was  o b s er v ed   t h at  t h e   p o p u latio n   h as  co n v er g ed   to   th b est  v al u ea r lier   in   ca s o f   th s i m p le  g r a m m ar s ,   w h er ea s   it  h as  s h o w n   s lo co n v er g e n ce   f o r   r el ati v el y   co m p lex   g r a m m ar .   T h in v er ted   m u tatio n   o p er ato r   w i th   r an d o m   m as k s   an d   t h e n   XOR o p er atio n   in tr o d u ce s   s u f f icie n t d i v er s it y   in   th e   p o p u lat io n   h elp s   i n   a v o id in g   p r e m at u r co n v er g en ce   th a is   th m ai n   r ea s o n t h au t h o r   h as  co m p ar ed   th alg o r ith m   w it h   t h e x is tin g   G A   p r o p o s ed   f o r   av o id in g   p r em at u r co n v er g e n ce .       4 . 4   St a t is t ica l A na ly s is   A   s tati s tical  te s h as  b ee n   p er f o r m ed   co n s id er in g   t h h y p o t h esi s th ere  is   n o   s ig n ifica n t   d iffer en ce   in   th mea n   o s a mp les  a t h 5 leve o co n fid en ce ”.   T o tal  1 5   s a m p les  h a v b ee n   d r a w n   f r o m   ea c h   alg o r ith m   f o r   th r a n d o m l y   s e lecte d   lan g u a g e.   T h d escr ip ti v an a l y s is   is   d ep icted   in   T ab le  7   r ep r esen ts   t h e   m i n i m u m ,   m a x i m u m   a n d   av e r ag f it n es s .   T h m ai n   A NO VA   r es u lt  is   r ep r esen ted   in   T ab le  6 .   T h p -   v alu e   0 . 0 0 1 < 0 . 0 5   lea d s   t o   r e j ec tio n   o f   n u ll  h y p o th e s is .   T h er ef o r e,   m u ltip le  co m p ar is o n   te s ts T u k e y HS test   h a s   b ee n   ad ap ted .   T h r esu lt s   o f   T u k e y HS test   is   d ep icted   i n   T ab le  8   in d icate s   t h at  t h p er f o r m a n ce   o f   t h GI GA  is   s i g n i f ica n tl y   b etter   t h an   C G A   a n d   R OGG s i n ce   th p - v a lu e   0 . 0 0 2   an d   0 . 0 5   is   eith er   le s s   o r   eq u al   to   th 0 . 0 5 ,   w h er ea s   th p r o p o s ed   GI GA   w i th   P D A   s i m u lato r   p er f o r m   b etter   th a n   t h cr o w d in g   m et h o d .   Fig u r 4   g r ap h ical l y   d i s p la y s   th a v er ag f it n es s   v a lu o f   ea ch   al g o r ith m .   T h X - a x i s   r ep r esen t s   t h m et h o d s   an d   th e   Y - a x i s   r ep r es en ts   th e   esti m ated   m ar g in a l a v er ag f itn e s s .   T h a v er ag e   f itn ess   o f   t h GI G is   f o u n d   b etter   th an   o t h er   ap p r o a ch es.  T h C G A‟ s   p er f o r m an ce   h as b ee n   f o u n d   w o r s t.       T ab le  6 .   A NOV A   tab le  s h o w i n g   g r o u p   co m p ar is o n   r es u lt s     S u m o f   S q u a r e s   df   M e a n   S q u a r e   F   S i g .   B e t w e e n   G r o u p s   3 1 9 3 8 2 . 8 3 6   3   1 0 6 4 6 0 . 9 4 5   6 . 3 8 9   0 0 1   W i t h i n   G r o u p s   9 3 3 1 4 9 . 0 3 3   56   1 6 6 6 3 . 3 7 6       T o t a l   1 2 5 2 5 3 1 . 8 7 0   59               Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - AI     I SS N:  2252 - 8938       Gen etic  A lg o r ith fo r   Gra mm a r   I n d u ctio n   a n d   R u les V erif ica tio n   th r o u g h   a ...   ( Ha r i Mo h a n   P a n d ey )   109   T ab le  7 .   Descr ip tiv an al y s is   M e t h o d   N   M e a n   S t d .   D e v i a t i o n   S t d .   Er r o r   9 5 C o n f i d e n c e   I n t e r v a l   f o r   M e a n   M i n i m u m   M a x i m u m   L o w e r   B o u n d   U p p e r   B o u n d   C G A   15   7 4 7 . 9 8 6 7   1 3 8 . 7 6 4 7 1   3 5 . 8 2 8 8 9   6 7 1 . 1 4 1 3   8 2 4 . 8 3 2 0   5 4 0 . 2 0   9 4 4 . 5 0   R O G G A   15   7 5 9 . 3 8 6 7   1 3 9 . 4 5 0 4 9   3 6 . 0 0 5 9 6   6 8 2 . 1 6 1 6   8 3 6 . 6 1 1 8   5 6 0 . 3 0   9 5 0 . 5 0   C r o w d i n g   15   8 5 5 . 9 9 3 3   1 1 2 . 4 8 9 4 0   2 9 . 0 4 4 6 4   7 9 3 . 6 9 8 8   9 1 8 . 2 8 7 9   6 3 4 . 8 0   1 0 0 3 . 0 0   G I G A   15   9 2 5 . 6 2 6 7   1 2 3 . 6 8 3 2 8   3 1 . 9 3 4 8 9   8 5 7 . 1 3 3 1   9 9 4 . 1 2 0 2   6 1 5 . 9 0   1 0 1 1 . 8 0   T o t a l   60   8 2 2 . 2 4 8 3   1 4 5 . 7 0 2 9 6   1 8 . 8 1 0 1 7   7 8 4 . 6 0 9 3   8 5 9 . 8 8 7 4   5 4 0 . 2 0   1 0 1 1 . 8 0       T ab le  8 .   Mu ltip le  co m p ar is o n s   test   ( P o s th o test : T u k e y   HS test )   ( I )   M e t h o d   ( J)   M e t h o d   M e a n   D i f f e r e n c e   ( I - J)   S t d .   Er r o r   S i g .   9 5 C o n f i d e n c e   I n t e r v a l   L o w e r   B o u n d   U p p e r   B o u n d   C G A   R O G G A   - 1 1 . 4 0 0 0 0   4 7 . 1 3 5 8 0   . 9 9 5   - 1 3 6 . 2 1 0 3   1 1 3 . 4 1 0 3   C r o w d i n g   - 1 0 8 . 0 0 6 6 7   4 7 . 1 3 5 8 0   . 1 1 2   - 2 3 2 . 8 1 6 9   1 6 . 8 0 3 6   G I G A   - 1 7 7 . 6 4 0 0 0 *   4 7 . 1 3 5 8 0   . 0 0 2   - 3 0 2 . 4 5 0 3   - 5 2 . 8 2 9 7   R O G G A   C G A   1 1 . 4 0 0 0 0   4 7 . 1 3 5 8 0   . 9 9 5   - 1 1 3 . 4 103   1 3 6 . 2 1 0 3   C r o w d i n g   - 9 6 . 6 0 6 6 7   4 7 . 1 3 5 8 0   . 1 8 3   - 2 2 1 . 4 1 6 9   2 8 . 2 0 3 6   G I G A   - 1 6 6 . 2 4 0 0 0 *   4 7 . 1 3 5 8 0   . 0 0 5   - 2 9 1 . 0 5 0 3   - 4 1 . 4 2 9 7   C r o w d i n g   C G A   1 0 8 . 0 0 6 6 7   4 7 . 1 3 5 8 0   . 1 1 2   - 1 6 . 8 0 3 6   2 3 2 . 8 1 6 9   R O G G A   9 6 . 6 0 6 6 7   4 7 . 1 3 5 8 0   . 1 8 3   - 2 8 . 2 0 3 6   2 2 1 . 4 1 6 9   G I G A   - 6 9 . 6 3 3 3 3   4 7 . 1 3 5 8 0   . 4 5 8   - 1 9 4 . 4 4 3 6   5 5 . 1 7 6 9   G I G A   C G A   1 7 7 . 6 4 0 0 0 *   4 7 . 1 3 5 8 0   . 0 0 2   5 2 . 8 2 9 7   3 0 2 . 4 5 0 3   R O G G A   1 6 6 . 2 4 0 0 0 *   4 7 . 1 3 5 8 0   . 0 0 5   4 1 . 4 2 9 7   2 9 1 . 0 5 0 3   C r o w d i n g   6 9 . 6 3 3 3 3   4 7 . 1 3 5 8 0   . 4 5 8   - 5 5 . 1 7 6 9   1 9 4 . 4 4 3 6   * .   T h e   me a n   d i f f e r e n c e   i s s i g n i f i c a n t   a t   t h e   0 . 0 5   l e v e l .           Fig u r 4 .   Me an s   o f   a v e r ag f it n es s   w it h   r esp ec t to   th alg o r it h m s   ( m et h o d s )   ch ar t       5.   CO NCLU SI O N   I n   th i s   p ap er ,   th GI GA   h as  b ee n   p r esen ted   f o r   C FG  i n d u ctio n .   T h r esu lts   r ep o r ted   p r o v id th e   s ig n i f ica n e v id en ce   ab o u t h e   p er f o r m an ce   o f   th e   p r o p o s ed   alg o r it h m .   T h 2 - le v el  o r t h o g o n al   ar r a y   a n d   t h e   T ag u ch m eth o d s   SN R   h a v e   b ee n   in co r p o r ated   to   f in d   th ap p r o p r iate  p a r am eter s   s e tt in g   t h at  i n tr o d u ce s   r o b u s tn es s ,   f as co n v er g en ce   a n d   s tatis t ical  s o u n d n es s .   T h a u th o r   h a s   ex ec u ted   th p r o p o s ed   GI GA   f o r   C F L s   an d   r eg u lar   la n g u a g es   o f   v ar y in g   co m p le x itie s .   T h e x p er im en tal  r es u lt s   h av e   b ee n   f o u n d   en co u r ag in g   a s   t h e   p r o p o s ed   GI GA   h a s   b ee n   f o u n d   ca p ab le  in   C FG  i n d u ctio n   an d   g r ea tl y   i m p r o v e s   th p er f o r m a n ce .   T h P DA   s i m u lato r   h as   b ee n   in co r p o r ated   in   th e   ex p er i m en ts   h a v e   b ee n   f o u n d   w o r k i n g   s u cc e s s f u ll y   f o r   t h li g h w ei g h e x a m p le s ,   w h ic h   ca n   b i m p r o v ed   f o r   th e   lar g er   le n g th   d escr ip tio n   o f   th e   tr ain i n g   d ata  s et.   T h r esu lt  r ec eiv ed   ap p ly in g   p r o p o s ed   alg o r ith m   h as  b ee n   co m p ar ed   w it h   o t h er   ap p r o ac h es  in d icat es  th s u p er io r it y   o f   th GI G A .   T h e   au th o r   h as  p e r f o r m ed   s tatis tical  test s   ex p lai n s   t h p er f o r m an ce   s ig n i f ica n ce   o f   th p r o p o s e d   ap p r o ac h .   T h cu r r en t r esu l ts   ar en co u r ag i n g   b u t it  w o u ld   b in ter esti n g   to   i m p le m e n t th p r o p o s ed   ap p r o ac h   Evaluation Warning : The document was created with Spire.PDF for Python.