Article

A prolog toolkit for formal languages and automata

Authors:

Michel Wermelinger,

Artur Miguel DiasAuthors Info & Claims

ITiCSE '05: Proceedings of the 10th annual SIGCSE conference on Innovation and technology in computer science education

Pages 330 - 334

https://doi.org/10.1145/1067445.1067536

Published: 27 June 2005 Publication History

Get Access

Abstract

This paper describes the first version of PFLAT (read "P flat"), a collection of Prolog predicates that aims to provide a pedagogical implementation of concepts and algorithms taught in Formal Languages and Automata Theory (FLAT) courses. By ``pedagogical implementation'' we mean on the one hand that students should be able to easily map the implementation to the mathematical definitions given in lectures, and on the other hand that the toolkit should provide a library for students to implement further concepts and algorithms. In both cases the goal is to make students more confident in defining and manipulating the various kinds of languages and automata at a level beyond the one provided by visual simulators of automata. As such, PFLAT is not intended to replace but rather complement existing graphical tools. We believe the declarative, non-deterministic, and interactive nature of Prolog helps in building an executable specification of FLAT concepts and definitions that can be actively extended and explored by students, in order to achieve the stated goal.

References

[1]

C. I. Chesñevar, M. L. Cobo, and W. Yurcik. Using theoretical computer simulators for formal languages and automata theory. SIGCSE Bulletin, 35(2):33--37, 2003.

Digital Library

Google Scholar

[2]

D. Crookes. Using Prolog to present abstract machines. SIGCSE Bulletin, 20(3):8--12, 1988.

Digital Library

Google Scholar

[3]

J. L. Hein. A declarative laboratory approach for discrete structures, logic, and computability. SIGCSE Bulletin, 25(3):19--25, 1993.

Digital Library

Google Scholar

[4]

J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

Digital Library

Google Scholar

[5]

L. Monteiro. Second author. Formal languages and automata. 298 slides, Univ. Nova de Lisboa, 2003. In Portuguese.

Google Scholar

[6]

L. Monteiro, M. Wermelinger, M. Mamede, and L. Caires.Authors and colleagues. Formal languages and automata exercises. Handout, 2002. 16 pages.

Google Scholar

[7]

L. Sterling and E. Shapiro. The Art of Prolog. MIT Press, 2nd edition, 1994.

Google Scholar

[8]

G. van Noord. FSA utilities: A toolbox to manipulate finite-state automata. In Automata Implementation, LNCS 1260. Springer Verlag, 1997.

Digital Library

Google Scholar

Cited By

View all

Moura P(2011)Programming Patterns for Logtalk Parametric ObjectsApplications of Declarative Programming and Knowledge Management10.1007/978-3-642-20589-7_4(52-69)Online publication date: 2011
https://doi.org/10.1007/978-3-642-20589-7_4
Moura P(2009)Programming patterns for logtalk parametric objectsProceedings of the 18th international conference on Applications of declarative programming and knowledge management10.5555/2008383.2008389(52-69)Online publication date: 3-Nov-2009
https://dl.acm.org/doi/10.5555/2008383.2008389
Frede CKnobelsdorf M(2020)A differentiated picture of student performance in introductory courses to theory of computationComputer Science Education10.1080/08993408.2020.1809946(1-25)Online publication date: 4-Oct-2020
https://doi.org/10.1080/08993408.2020.1809946
Show More Cited By

Index Terms

A prolog toolkit for formal languages and automata

Recommendations

A prolog toolkit for formal languages and automata

This paper describes the first version of PFLAT (read "P flat"), a collection of Prolog predicates that aims to provide a pedagogical implementation of concepts and algorithms taught in Formal Languages and Automata Theory (FLAT) courses. By ``...
Limited Automata and Context-Free Languages
Non-Classical Models of Automata and Applications V

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence ...
Bideterministic automata and minimal representations of regular languages
Implementation and application of automata

Bideterministic automata are deterministic automata with the property of their reversal automata also being deterministic. It has been known that a bideterministic automaton is the minimal deterministic automaton accepting its language. This paper shows ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ITiCSE '05: Proceedings of the 10th annual SIGCSE conference on Innovation and technology in computer science education

June 2005

440 pages

ISBN:1595930248

DOI:10.1145/1067445

Conference Chairs:
José Cunha
Universidade Nova de Lisboa, Portugal
,
William Fleischman
Villanova University
,
Program Chairs:
Viera K. Proulx
Northeastern University
,
João Lourenço
Universidade Nova de Lisboa, Portugal

ACM SIGCSE Bulletin Volume 37, Issue 3
September 2005
418 pages
ISSN:0097-8418
DOI:10.1145/1151954
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ITiCSE05

Sponsor:

ITiCSE05: Innovation and Technology in Computer Science Education

June 27 - 29, 2005

Caparica, Portugal

Acceptance Rates

Overall Acceptance Rate 552 of 1,613 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
400
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Moura P(2011)Programming Patterns for Logtalk Parametric ObjectsApplications of Declarative Programming and Knowledge Management10.1007/978-3-642-20589-7_4(52-69)Online publication date: 2011
https://doi.org/10.1007/978-3-642-20589-7_4
Moura P(2009)Programming patterns for logtalk parametric objectsProceedings of the 18th international conference on Applications of declarative programming and knowledge management10.5555/2008383.2008389(52-69)Online publication date: 3-Nov-2009
https://dl.acm.org/doi/10.5555/2008383.2008389
Frede CKnobelsdorf M(2020)A differentiated picture of student performance in introductory courses to theory of computationComputer Science Education10.1080/08993408.2020.1809946(1-25)Online publication date: 4-Oct-2020
https://doi.org/10.1080/08993408.2020.1809946
Frede CKnobelsdorf MMalmi LKorhonen AMcCartney RPetersen AMalmi LMcCartney R(2018)Exploring how Students Perform in a Theory of Computation Course using Final Exam and Homework Assignments DataProceedings of the 2018 ACM Conference on International Computing Education Research10.1145/3230977.3230996(241-249)Online publication date: 8-Aug-2018
https://dl.acm.org/doi/10.1145/3230977.3230996
Knobelsdorf MFrede CSheard JTenenberg JChinn DDorn B(2016)Analyzing Student Practices in Theory of Computation in Light of Distributed Cognition TheoryProceedings of the 2016 ACM Conference on International Computing Education Research10.1145/2960310.2960331(73-81)Online publication date: 25-Aug-2016
https://dl.acm.org/doi/10.1145/2960310.2960331
Eremondi JHosking AEugster P(2013)The poor man's proof assistantProceedings of the 2013 companion publication for conference on Systems, programming, & applications: software for humanity10.1145/2508075.2527300(101-102)Online publication date: 26-Oct-2013
https://dl.acm.org/doi/10.1145/2508075.2527300
Eremondi JHosking AEugster P(2013)The poor man's proof assistantProceedings of the 2013 companion publication for conference on Systems, programming, & applications: software for humanity10.1145/2508075.2508088(75-76)Online publication date: 26-Oct-2013
https://dl.acm.org/doi/10.1145/2508075.2508088
Pillay N(2010)Learning difficulties experienced by students in a course on formal languages and automata theoryACM SIGCSE Bulletin10.1145/1709424.170944441:4(48-52)Online publication date: 18-Jan-2010
https://dl.acm.org/doi/10.1145/1709424.1709444
Chakraborty PSaxena PKatti C(2010)A compiler‐based toolkit to teach and learn finite automataComputer Applications in Engineering Education10.1002/cae.2049221:3(467-474)Online publication date: 13-Oct-2010
https://doi.org/10.1002/cae.20492

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A prolog toolkit for formal languages and automata

Limited Automata and Context-Free Languages

Bideterministic automata and minimal representations of regular languages