47:
Machine transitions are based on the current state and input symbol, and also the current topmost symbol of the stack. Symbols lower in the stack are not visible and have no immediate effect. Machine actions include pushing, popping, or replacing the stack top. A deterministic pushdown automaton
495:
1192:
Closure properties of deterministic context-free languages (accepted by deterministic PDA by final state) are drastically different from the context-free languages. As an example they are (effectively) closed under complementation, but not closed under union. To prove that the complement of a
1196:
As a consequence of the complementation it is decidable whether a deterministic PDA accepts all words over its input alphabet, by testing its complement for emptiness. This is not possible for context-free grammars (hence not for general PDA).
1193:
language accepted by a deterministic PDA is also accepted by a deterministic PDA is tricky because one has to avoid infinite computations and correctly handle transitions that manipulate the stack without reading input symbols.
398:
751:
169:
882:
933:
1328:
1290:
1205:
Géraud Sénizergues (1997) proved that the equivalence problem for deterministic PDA (i.e. given two deterministic PDA A and B, is L(A)=L(B)?) is decidable, a proof that earned him the 2002
1667:
1123:
on the alphabet of 0 and 1 has the context-free grammar S → 0S0 | 1S1 | ε. If a DPDA for this language exists, and it sees a string 0, it must use its stack to memorize the length
316:
834:
648:
793:
346:
48:
has at most one legal transition for the same combination of input symbol, state, and top stack symbol. This is where it differs from the nondeterministic pushdown automaton.
279:
962:
611:
571:
548:
389:
242:
219:
591:
1051:, it can also be accepted by a DPDA if and only if there is a single computation from the initial configuration until an accepting one for all strings belonging to
1107:
1078:
1029:
975:. The two are not equivalent for the deterministic pushdown automaton (although they are for the non-deterministic pushdown automaton). The languages accepted by
196:
1049:
672:
517:
366:
77:
1987:
1660:
490:{\displaystyle \delta \colon (Q\,\times (\Sigma \,\cup \left\{\varepsilon \,\right\})\times \Gamma \,)\longrightarrow {\mathcal {P}}(Q\times \Gamma ^{*})}
692:
1874:
1653:
1523:
1109:
can be accepted by a PDA it is a context free language and if it can be accepted by a DPDA it is a deterministic context-free language (DCFL).
85:
1466:
1799:
991:
1889:
37:
1112:
Not all context-free languages are deterministic. This makes the DPDA a strictly weaker device than the PDA. For example, the language
1814:
1622:
1608:
1450:
1300:
1273:
1246:
1179:, which is a proper subclass of the DCFL. In the case of a PDA, this restriction has no effect on the class of languages accepted.
1982:
839:
2029:
1843:
2034:
887:
1860:
1785:
1638:
1957:
1152:
comparing the post-"11" length to the pre-"11" length will make the stack empty again. For this reason, the strings
1853:
2039:
1778:
1930:
1925:
1442:
2011:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
1941:
1879:
1804:
286:
801:
1884:
1832:
1645:
41:
620:
756:
323:
1977:
1952:
1809:
1770:
249:
1334:
938:
596:
556:
1962:
1904:
1848:
1632:
1365:
526:
33:
1614:
373:
226:
203:
1697:
1618:
1462:
1296:
1269:
1263:
1242:
1238:
1231:
576:
1946:
1899:
1866:
1712:
1604:
1579:
1532:
1454:
1396:
1357:
983:
and are prefix-free: no word in the language is the prefix of another word in the language.
1909:
1824:
1791:
1707:
1680:
1676:
1083:
1054:
1005:
17:
180:
1920:
1702:
1684:
1324:
1320:
1226:
1206:
1176:
1034:
657:
502:
351:
62:
1584:
1551:
1536:
1476:
1401:
1384:
1175:
Restricting the DPDA to a single state reduces the class of languages accepted to the
2023:
2005:
1316:
1445:(1997). "The equivalence problem for deterministic pushdown automata is decidable".
1369:
614:
551:
1418:
1972:
1894:
1819:
746:{\displaystyle q\in Q,a\in \Sigma \cup \left\{\varepsilon \right\},x\in \Gamma }
520:
1458:
1120:
651:
164:{\displaystyle M=(Q\,,\Sigma \,,\Gamma \,,q_{0}\,,Z_{0}\,,A\,,\delta \,)}
1361:
1935:
990:, and it is this acceptance criterion which is used to define the
1447:
Proc. Int. Coll. on
Automata, Languages, and Programming (ICALP)
1127:, in order to be able to distinguish its possible continuations
1649:
1289:
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2006).
2004:
Each category of languages, except those marked by a , is a
626:
460:
1330:
Introduction to
Automata Theory, Languages, and Computation
1292:
Introduction to
Automata Theory, Languages, and Computation
877:{\displaystyle \delta (q,\varepsilon ,x)\not =\emptyset \,}
36:. The class of deterministic pushdown automata accepts the
967:
There are two possible acceptance criteria: acceptance by
1613:. Upper Saddle River, NJ 07458: Prentice Hall. pp.
1348:
Kurki-Suonio, R. (1969). "Notes on top-down languages".
1209:. For nondeterministic PDA, equivalence is undecidable.
1521:)? decidability results from complete formal systems".
1494:(Technical Report 1161-97). Universite Bordeaux, LaBRI.
1268:(3rd ed.). World Scientific. pp. 193, 195.
1086:
1057:
1037:
1008:
941:
890:
842:
804:
759:
695:
660:
623:
599:
579:
559:
529:
505:
401:
376:
354:
326:
289:
252:
229:
206:
183:
88:
65:
1417:
Hopcroft, John E.; Ullman, Jeffrey D. (1969-01-01),
928:{\displaystyle \delta \left(q,a,x\right)=\emptyset }
1295:(3rd ed.). Addison-Wesley. pp. 234, 254.
1425:, USA: Addison-Wesley Longman Publishing Co., Inc.
1230:
1101:
1072:
1043:
1023:
956:
927:
876:
828:
787:
745:
666:
642:
605:
585:
565:
542:
511:
489:
383:
360:
340:
310:
273:
236:
213:
190:
163:
71:
550:is "the set of all finite strings (including the
1505:Géraud Sénizergues (2001). "Fundamental study:
1423:Formal languages and their relation to automata
1385:"Properties of Deterministic Top Down Grammars"
685:if it satisfies both the following conditions:
1610:Logic and Language Models for Computer Science
1661:
1265:An Introduction To The Analysis Of Algorithms
8:
1983:Counter-free (with aperiodic finite monoid)
1383:Rosenkrantz, D. J.; Stearns, R. E. (1970).
1693:
1668:
1654:
1646:
1583:
1400:
1233:Introduction to the Theory of Computation
1085:
1056:
1036:
1007:
979:are those languages that are accepted by
940:
889:
873:
841:
803:
784:
758:
694:
659:
625:
624:
622:
598:
578:
558:
534:
528:
504:
478:
459:
458:
451:
436:
424:
414:
400:
380:
375:
368:is the set of accepting, or final, states
353:
337:
330:
325:
307:
300:
294:
288:
270:
263:
257:
251:
233:
228:
210:
205:
187:
182:
157:
150:
143:
137:
129:
123:
115:
108:
101:
87:
64:
1333:(2 ed.). Addison-Wesley. pp.
1218:
1875:Linear context-free rewriting language
1630:
1800:Linear context-free rewriting systems
7:
1453:. Vol. 1256. pp. 671–681.
992:deterministic context-free languages
311:{\displaystyle Z_{0}\,\in \Gamma \,}
38:deterministic context-free languages
1568:)? A simplified decidability proof"
829:{\displaystyle q\in Q,x\in \Gamma }
2008:of the category directly above it.
986:The usual acceptance criterion is
948:
922:
870:
823:
740:
714:
580:
531:
475:
448:
421:
304:
230:
207:
112:
105:
56:A (not necessarily deterministic)
14:
1451:Lecture Notes in Computer Science
1419:"Deterministic pushdown automata"
1262:Soltys-kulinicz, Michael (2018).
643:{\displaystyle {\mathcal {P}}(X)}
1031:is a language accepted by a PDA
788:{\displaystyle \delta (q,a,x)\,}
341:{\displaystyle A\,\subseteq Q\,}
244:is a finite set of stack symbols
221:is a finite set of input symbols
22:deterministic pushdown automaton
391:is a transition function, where
1096:
1090:
1067:
1061:
1018:
1012:
864:
846:
781:
763:
637:
631:
484:
465:
455:
452:
442:
418:
408:
274:{\displaystyle q_{0}\,\in Q\,}
158:
95:
1:
1585:10.1016/S0304-3975(02)00027-0
1537:10.1016/S0304-3975(00)00285-1
1402:10.1016/s0019-9958(70)90446-8
957:{\displaystyle a\in \Sigma .}
79:can be defined as a 7-tuple:
1572:Theoretical Computer Science
1524:Theoretical Computer Science
606:{\displaystyle \varepsilon }
566:{\displaystyle \varepsilon }
318:is the starting stack symbol
1550:Géraud Sénizergues (2002).
1475:Géraud Sénizergues (1997).
543:{\displaystyle \Gamma ^{*}}
2056:
1890:Deterministic context-free
1815:Deterministic context-free
1237:. PWS Publishing. p.
2001:
1963:Nondeterministic pushdown
1691:
1459:10.1007/3-540-63165-8_221
1172:cannot be distinguished.
384:{\displaystyle \delta \,}
237:{\displaystyle \Gamma \,}
214:{\displaystyle \Sigma \,}
198:is a finite set of states
1637:: CS1 maint: location (
795:has at most one element.
32:) is a variation of the
1389:Information and Control
586:{\displaystyle \Gamma }
2030:Automata (computation)
1968:Deterministic pushdown
1844:Recursively enumerable
1473:— Full version:
1103:
1074:
1045:
1025:
958:
929:
878:
830:
789:
747:
668:
644:
607:
587:
567:
544:
513:
491:
385:
362:
342:
312:
275:
238:
215:
192:
165:
73:
42:context-free languages
2035:Models of computation
1407:Here: p.246–247
1148:Hence, after reading
1104:
1075:
1046:
1026:
959:
930:
879:
831:
790:
748:
669:
645:
608:
588:
568:
545:
514:
492:
386:
363:
343:
313:
276:
239:
216:
193:
166:
74:
40:, a proper subset of
1953:Tree stack automaton
1102:{\displaystyle L(A)}
1084:
1073:{\displaystyle L(A)}
1055:
1035:
1024:{\displaystyle L(A)}
1006:
998:Languages recognized
939:
888:
840:
802:
757:
693:
658:
621:
597:
577:
557:
527:
503:
399:
374:
352:
324:
287:
250:
227:
204:
181:
86:
63:
1861:range concatenation
1786:range concatenation
1443:Sénizergues, Géraud
1201:Equivalence problem
191:{\displaystyle Q\,}
1603:Hamburger, Henry;
1362:10.1007/BF01946814
1099:
1070:
1041:
1021:
971:and acceptance by
954:
925:
874:
826:
785:
743:
664:
640:
603:
583:
563:
540:
509:
487:
381:
358:
338:
308:
281:is the start state
271:
234:
211:
188:
161:
69:
34:pushdown automaton
2017:
2016:
1996:
1995:
1958:Embedded pushdown
1854:Context-sensitive
1779:Context-sensitive
1713:Abstract machines
1698:Chomsky hierarchy
1468:978-3-540-63165-1
1044:{\displaystyle A}
667:{\displaystyle X}
573:) of elements of
512:{\displaystyle *}
361:{\displaystyle A}
72:{\displaystyle M}
52:Formal definition
2047:
2040:Formal languages
2012:
2009:
1973:Visibly pushdown
1947:Thread automaton
1895:Visibly pushdown
1863:
1820:Visibly pushdown
1788:
1775:(no common name)
1694:
1681:formal languages
1670:
1663:
1656:
1647:
1642:
1636:
1628:
1605:Dana S. Richards
1590:
1589:
1587:
1578:(1–2): 555–608.
1547:
1541:
1540:
1502:
1496:
1495:
1472:
1439:
1433:
1432:
1431:
1430:
1414:
1408:
1406:
1404:
1380:
1374:
1373:
1345:
1339:
1338:
1313:
1307:
1306:
1286:
1280:
1279:
1259:
1253:
1252:
1236:
1223:
1171:
1164:0 11 0 0 11 0 ∉
1161:
1154:0 11 0 0 11 0 ∈
1151:
1147:
1136:
1108:
1106:
1105:
1100:
1079:
1077:
1076:
1071:
1050:
1048:
1047:
1042:
1030:
1028:
1027:
1022:
963:
961:
960:
955:
934:
932:
931:
926:
918:
914:
883:
881:
880:
875:
835:
833:
832:
827:
794:
792:
791:
786:
752:
750:
749:
744:
730:
673:
671:
670:
665:
649:
647:
646:
641:
630:
629:
612:
610:
609:
604:
592:
590:
589:
584:
572:
570:
569:
564:
549:
547:
546:
541:
539:
538:
518:
516:
515:
510:
496:
494:
493:
488:
483:
482:
464:
463:
441:
437:
390:
388:
387:
382:
367:
365:
364:
359:
347:
345:
344:
339:
317:
315:
314:
309:
299:
298:
280:
278:
277:
272:
262:
261:
243:
241:
240:
235:
220:
218:
217:
212:
197:
195:
194:
189:
170:
168:
167:
162:
142:
141:
128:
127:
78:
76:
75:
70:
2055:
2054:
2050:
2049:
2048:
2046:
2045:
2044:
2020:
2019:
2018:
2013:
2010:
2003:
1997:
1992:
1914:
1858:
1837:
1783:
1764:
1687:
1685:formal grammars
1677:Automata theory
1674:
1629:
1625:
1602:
1599:
1597:Further reading
1594:
1593:
1549:
1548:
1544:
1504:
1503:
1499:
1474:
1469:
1441:
1440:
1436:
1428:
1426:
1416:
1415:
1411:
1382:
1381:
1377:
1347:
1346:
1342:
1315:
1314:
1310:
1303:
1288:
1287:
1283:
1276:
1261:
1260:
1256:
1249:
1225:
1224:
1220:
1215:
1203:
1190:
1185:
1177:LL(1) languages
1170:
1163:
1160:
1153:
1149:
1145:
1138:
1135:
1128:
1119:of even-length
1118:
1082:
1081:
1053:
1052:
1033:
1032:
1004:
1003:
1000:
937:
936:
898:
894:
886:
885:
838:
837:
800:
799:
755:
754:
720:
691:
690:
656:
655:
619:
618:
595:
594:
575:
574:
555:
554:
530:
525:
524:
523:, meaning that
501:
500:
474:
432:
428:
397:
396:
372:
371:
350:
349:
322:
321:
290:
285:
284:
253:
248:
247:
225:
224:
202:
201:
179:
178:
133:
119:
84:
83:
61:
60:
54:
18:automata theory
12:
11:
5:
2053:
2051:
2043:
2042:
2037:
2032:
2022:
2021:
2015:
2014:
2002:
1999:
1998:
1994:
1993:
1991:
1990:
1988:Acyclic finite
1985:
1980:
1975:
1970:
1965:
1960:
1955:
1949:
1944:
1939:
1938:Turing Machine
1933:
1931:Linear-bounded
1928:
1923:
1921:Turing machine
1917:
1915:
1913:
1912:
1907:
1902:
1897:
1892:
1887:
1882:
1880:Tree-adjoining
1877:
1872:
1869:
1864:
1856:
1851:
1846:
1840:
1838:
1836:
1835:
1830:
1827:
1822:
1817:
1812:
1807:
1805:Tree-adjoining
1802:
1797:
1794:
1789:
1781:
1776:
1773:
1767:
1765:
1763:
1762:
1759:
1756:
1753:
1750:
1747:
1744:
1741:
1738:
1735:
1732:
1729:
1726:
1723:
1719:
1716:
1715:
1710:
1705:
1700:
1692:
1689:
1688:
1675:
1673:
1672:
1665:
1658:
1650:
1644:
1643:
1623:
1598:
1595:
1592:
1591:
1542:
1531:(1–2): 1–166.
1497:
1467:
1434:
1409:
1395:(3): 226–256.
1375:
1356:(3): 225–238.
1340:
1325:Jeffrey Ullman
1321:Rajeev Motwani
1317:Hopcroft, John
1308:
1301:
1281:
1274:
1254:
1247:
1227:Michael Sipser
1217:
1216:
1214:
1211:
1202:
1199:
1189:
1186:
1184:
1181:
1168:
1158:
1143:
1133:
1116:
1098:
1095:
1092:
1089:
1069:
1066:
1063:
1060:
1040:
1020:
1017:
1014:
1011:
999:
996:
965:
964:
953:
950:
947:
944:
924:
921:
917:
913:
910:
907:
904:
901:
897:
893:
872:
869:
866:
863:
860:
857:
854:
851:
848:
845:
825:
822:
819:
816:
813:
810:
807:
796:
783:
780:
777:
774:
771:
768:
765:
762:
742:
739:
736:
733:
729:
726:
723:
719:
716:
713:
710:
707:
704:
701:
698:
676:
675:
663:
639:
636:
633:
628:
602:
582:
562:
537:
533:
508:
497:
486:
481:
477:
473:
470:
467:
462:
457:
454:
450:
447:
444:
440:
435:
431:
427:
423:
420:
417:
413:
410:
407:
404:
393:
392:
379:
369:
357:
336:
333:
329:
319:
306:
303:
297:
293:
282:
269:
266:
260:
256:
245:
232:
222:
209:
199:
186:
172:
171:
160:
156:
153:
149:
146:
140:
136:
132:
126:
122:
118:
114:
111:
107:
104:
100:
97:
94:
91:
68:
53:
50:
13:
10:
9:
6:
4:
3:
2:
2052:
2041:
2038:
2036:
2033:
2031:
2028:
2027:
2025:
2007:
2006:proper subset
2000:
1989:
1986:
1984:
1981:
1979:
1976:
1974:
1971:
1969:
1966:
1964:
1961:
1959:
1956:
1954:
1950:
1948:
1945:
1943:
1940:
1937:
1934:
1932:
1929:
1927:
1924:
1922:
1919:
1918:
1916:
1911:
1908:
1906:
1903:
1901:
1898:
1896:
1893:
1891:
1888:
1886:
1883:
1881:
1878:
1876:
1873:
1870:
1868:
1865:
1862:
1857:
1855:
1852:
1850:
1847:
1845:
1842:
1841:
1839:
1834:
1833:Non-recursive
1831:
1828:
1826:
1823:
1821:
1818:
1816:
1813:
1811:
1808:
1806:
1803:
1801:
1798:
1795:
1793:
1790:
1787:
1782:
1780:
1777:
1774:
1772:
1769:
1768:
1766:
1760:
1757:
1754:
1751:
1748:
1745:
1742:
1739:
1736:
1733:
1730:
1727:
1724:
1721:
1720:
1718:
1717:
1714:
1711:
1709:
1706:
1704:
1701:
1699:
1696:
1695:
1690:
1686:
1682:
1678:
1671:
1666:
1664:
1659:
1657:
1652:
1651:
1648:
1640:
1634:
1626:
1624:0-13-065487-6
1620:
1616:
1612:
1611:
1606:
1601:
1600:
1596:
1586:
1581:
1577:
1573:
1569:
1567:
1563:
1559:
1555:
1546:
1543:
1538:
1534:
1530:
1526:
1525:
1520:
1516:
1512:
1508:
1501:
1498:
1493:
1491:
1487:
1483:
1479:
1470:
1464:
1460:
1456:
1452:
1448:
1444:
1438:
1435:
1424:
1420:
1413:
1410:
1403:
1398:
1394:
1390:
1386:
1379:
1376:
1371:
1367:
1363:
1359:
1355:
1351:
1344:
1341:
1336:
1332:
1331:
1326:
1322:
1318:
1312:
1309:
1304:
1302:0-321-45536-3
1298:
1294:
1293:
1285:
1282:
1277:
1275:9789813235922
1271:
1267:
1266:
1258:
1255:
1250:
1248:0-534-94728-X
1244:
1240:
1235:
1234:
1228:
1222:
1219:
1212:
1210:
1208:
1200:
1198:
1194:
1187:
1182:
1180:
1178:
1173:
1167:
1157:
1142:
1132:
1126:
1122:
1115:
1110:
1093:
1087:
1064:
1058:
1038:
1015:
1009:
997:
995:
993:
989:
984:
982:
978:
974:
970:
951:
945:
942:
919:
915:
911:
908:
905:
902:
899:
895:
891:
867:
861:
858:
855:
852:
849:
843:
820:
817:
814:
811:
808:
805:
797:
778:
775:
772:
769:
766:
760:
737:
734:
731:
727:
724:
721:
717:
711:
708:
705:
702:
699:
696:
688:
687:
686:
684:
683:deterministic
680:
661:
653:
634:
616:
600:
560:
553:
535:
522:
506:
498:
479:
471:
468:
445:
438:
433:
429:
425:
415:
411:
405:
402:
395:
394:
377:
370:
355:
334:
331:
327:
320:
301:
295:
291:
283:
267:
264:
258:
254:
246:
223:
200:
184:
177:
176:
175:
154:
151:
147:
144:
138:
134:
130:
124:
120:
116:
109:
102:
98:
92:
89:
82:
81:
80:
66:
59:
51:
49:
45:
43:
39:
35:
31:
27:
23:
19:
1967:
1942:Nested stack
1885:Context-free
1810:Context-free
1771:Unrestricted
1609:
1575:
1571:
1565:
1561:
1557:
1553:
1545:
1528:
1522:
1518:
1514:
1510:
1506:
1500:
1489:
1485:
1481:
1477:
1446:
1437:
1427:, retrieved
1422:
1412:
1392:
1388:
1378:
1353:
1349:
1343:
1329:
1311:
1291:
1284:
1264:
1257:
1232:
1221:
1204:
1195:
1191:
1174:
1165:
1155:
1140:
1130:
1124:
1113:
1111:
1001:
987:
985:
980:
976:
972:
968:
966:
682:
678:
677:
615:empty string
613:denotes the
552:empty string
173:
57:
55:
46:
29:
25:
21:
15:
1951:restricted
1207:Gödel Prize
1121:palindromes
988:final state
981:final state
977:empty stack
973:final state
969:empty stack
521:Kleene star
2024:Categories
1429:2024-05-29
1183:Properties
935:for every
753:, the set
1905:Star-free
1859:Positive
1849:Decidable
1784:Positive
1708:Languages
1633:cite book
1139:0 11 0 ∉
1129:0 11 0 ∈
949:Σ
946:∈
923:∅
892:δ
871:∅
856:ε
844:δ
824:Γ
821:∈
809:∈
761:δ
741:Γ
738:∈
725:ε
718:∪
715:Σ
712:∈
700:∈
654:of a set
652:power set
601:ε
581:Γ
561:ε
536:∗
532:Γ
507:∗
480:∗
476:Γ
472:×
456:⟶
449:Γ
446:×
434:ε
426:∪
422:Σ
416:×
406::
403:δ
378:δ
332:⊆
305:Γ
302:∈
265:∈
231:Γ
208:Σ
155:δ
113:Γ
106:Σ
1703:Grammars
1607:(2002).
1370:60912010
1327:(2001).
1229:(1997).
868:≠
798:For any
689:For any
348:, where
1926:Decider
1900:Regular
1867:Indexed
1825:Regular
1792:Indexed
1188:Closure
1150:0 11 0,
884:, then
650:is the
519:is the
1978:Finite
1910:Finite
1755:Type-3
1746:Type-2
1728:Type-1
1722:Type-0
1621:
1617:–331.
1465:
1368:
1299:
1272:
1245:
617:, and
499:where
174:where
1936:PTIME
1366:S2CID
1337:–253.
1213:Notes
1080:. If
836:, if
1683:and
1639:link
1619:ISBN
1560:) =
1513:) =
1484:) =
1463:ISBN
1297:ISBN
1270:ISBN
1243:ISBN
1162:and
1137:and
26:DPDA
20:, a
1615:284
1580:doi
1576:281
1533:doi
1529:251
1455:doi
1397:doi
1358:doi
1350:BIT
1335:249
1239:102
1002:If
681:is
593:",
58:PDA
30:DPA
28:or
16:In
2026::
1679::
1635:}}
1631:{{
1574:.
1570:.
1527:.
1492:)?
1461:.
1449:.
1421:,
1393:17
1391:.
1387:.
1364:.
1352:.
1323:;
1319:;
1241:.
994:.
44:.
1871:—
1829:—
1796:—
1761:—
1758:—
1752:—
1749:—
1743:—
1740:—
1737:—
1734:—
1731:—
1725:—
1669:e
1662:t
1655:v
1641:)
1627:.
1588:.
1582::
1566:B
1564:(
1562:L
1558:A
1556:(
1554:L
1552:"
1539:.
1535::
1519:B
1517:(
1515:L
1511:A
1509:(
1507:L
1490:B
1488:(
1486:L
1482:A
1480:(
1478:L
1471:.
1457::
1405:.
1399::
1372:.
1360::
1354:9
1305:.
1278:.
1251:.
1169:p
1166:L
1159:p
1156:L
1146:.
1144:p
1141:L
1134:p
1131:L
1125:n
1117:p
1114:L
1097:)
1094:A
1091:(
1088:L
1068:)
1065:A
1062:(
1059:L
1039:A
1019:)
1016:A
1013:(
1010:L
952:.
943:a
920:=
916:)
912:x
909:,
906:a
903:,
900:q
896:(
865:)
862:x
859:,
853:,
850:q
847:(
818:x
815:,
812:Q
806:q
782:)
779:x
776:,
773:a
770:,
767:q
764:(
735:x
732:,
728:}
722:{
709:a
706:,
703:Q
697:q
679:M
674:.
662:X
638:)
635:X
632:(
627:P
485:)
469:Q
466:(
461:P
453:)
443:)
439:}
430:{
419:(
412:Q
409:(
356:A
335:Q
328:A
296:0
292:Z
268:Q
259:0
255:q
185:Q
159:)
152:,
148:A
145:,
139:0
135:Z
131:,
125:0
121:q
117:,
110:,
103:,
99:Q
96:(
93:=
90:M
67:M
24:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.