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