Essay on Languages, Grammars and Automata Theory

990 Words Jan 23rd, 2011 4 Pages
Languages, Grammars, and Automata Theory
Discrete Mathematics
Linda Chalk
Colorado Technical University
Professor Timothy Manzke
December 17, 2010

Languages, grammars and automata theory are all related to computer applications. Grammar is the rule for language structure regardless of the meaning. For computer programming languages context free grammar (CFG) is commonly used. Formal language as opposed to natural language must be used with computer applications because natural language is too vague for computer applications. Automata is a way to test an expression to determine if it is part of the language (Pfeifer, 2005).
A deterministic finite automata (DFA) is a machine that is the most simple to understand which will
…show more content…
Basically the BNF states what is allowed and what is not allowed when defining the grammar of a language (Garshol, 2007). The example below is taken from http://www.cs.utsa.edu/~wagner/CS3723/grammar/examples2.html.

Write a BNF grammar for the language of nonempty data files. A nonempty data file consists of one or more records, where each record is one or more fields. And let's say that each field is either integer (one or more digits) or string (one or more alphabetic or numeric characters enclosed in double quotes). Every record (including the last one) ends with a period. Every field (except the last one in a record) ends with a semicolon.
Solution #1 (repetitive): ::= { } ::= { ; } . ::= | ::= { } ::= " { } " ::= | ::= the usual stuff ::= the usual stuff Bubble sorting is the method for putting items in order. The technique starts by comparing the first variable to the second variable, the second variable to the third variable until it finds a variable out of order. When it finds one out of order it will swap positions then the sort will start over and continue until all variables are in order (bubble sort, n.d.). An example of bubble sort with data set {4, 5, 3, 2, 1}. The bubble sort starts by looking at the 4, 5

Related Documents