Automata and Formal Languages
Edit Page
Report
Scan day: 07 February 2014 UTC
-39
Virus safety - good
Description: A terse statement of important definitions and theorems in this field of study.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Automata and Formal Languages - finite automata 5-tuple (Q, Z, o, q0, F) q is set of states, q0 is start state, F is set of final states Z is finite input alphabet o is transition function from QxZ->Q that is o(q,a) returns a state for current state q and input symbol a from Z 1.) DFA: deterministic finite automata 2.) NFA: nondeterminisic finite automata 3.) NFA w/e: nondeterminisic finite automata with epsilon transitions 4.) regular expressions these four have equivalent power to handle regular languages terms language L L accepted by an automata L denoted by an expression two-way finite automata can move head as part of o(q,a) no more powerful moore vs mealy machines application of FA with output moore - output depends on current state mealy - output depends on current state and input symbol moore and mealy are equivalent pumping lemma used to show languages nonregular Let L be a regular set. Then there is a constant n such that if z is any word in L, and |z| >= n, we may write z=uvw in such a way that |uv|=1, and for all i>=0, uv^iw is in L. Furthermore, n is no greater than the number of states of the samllest FA accepting L. regular sets are closed under union, concatenation, kleene closure complement intersection substitution homomorphisms and inverse homomorphisms quotient with arbitrary sets the set of sentences accepted by an FA M with n states is: nonempty iff the FA accepts a sentence of length less than n infinite iff the FA accepts a sentence of length l where n a, A is variable, a is string from (V union T)* S is start symbol terminology language L generated by grammar G derivations derivation trees leftmost and rightmost derivations leftmost = at each step in a derivation a production is applied to the leftmost variable ambiguity a CFG G such that some word has two parse trees is said to be ambiguous or: some word that has more that one leftmost (or rightmost) derivation a CFL for which every CFG is amb
Size: 2048 chars
Contact Information
Email: —
Phone&Fax: —
Address: —
Extended: —
WEBSITE Info
| Page title: | |
| Keywords: | |
| Description: | |
| IP-address: | 173.164.201.41 |
WHOIS Info
| NS | Name Server: NS35.DOMAINCONTROL.COM Name Server: NS36.DOMAINCONTROL.COM |
| WHOIS | Status: clientDeleteProhibited Status: clientRenewProhibited Status: clientTransferProhibited Status: clientUpdateProhibited |
| Date | Creation Date: 15-sep-1997 Expiration Date: 14-sep-2019 |