Understanding Formal Languages and Automata Theory
Explore the concept of formal languages and automata theory, including language concatenation, recognizing languages with machines, and finite automata. Learn about simple automata examples and deterministic finite automata (DFA) definitions in this insightful overview.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Languages Given an alphabet , we can make a word or string by concatenating the letters of . Concatenation of x and y is xy Typical example: ={0,1}, the possible words over are the finite bit strings. A language is a set of words.
More about Languages The empty string is the unique string with zero length. Concatenation of two langauges: A B = { xy | x A and y B } Typical examples: L = { x | x is a bit string with two zeros } L = { anbn| n N } L = {1n | n is prime}
A Word of Warning Do not confuse the concatenation of languages with the Cartesian product of sets. For example, let A = {0,00} then A A = { 00, 000, 0000 } with |A A|=3, A A = { (0,0), (0,00), (00,0), (00,00) } with |A A|=4
Recognizing Languages Let L be a language S a machine M recognizes L if if and only if x L accept x S M if and only if x L reject
Finite Automaton The most simple machine that is not just a finite list of words. Read once , no write procedure. Typical is its limited memory. Think cell-phone, elevator door, etc.
A Simple Automaton (0) transition rules states 0 1 1 0 q1 q2 q3 0,1 starting state accepting state
A Simple Automaton (1) 0 1 1 0 q1 q2 q3 start 0,1 accept on input 0110 , the machine goes: q1 q1 q2 q2 q3 = reject
A Simple Automaton (2) 0 1 1 0 q1 q2 q3 0,1 on input 101 , the machine goes: q1 q2 q3 q2 = accept
A Simple Automaton (3) 0 1 1 0 q1 q2 q3 0,1 010: reject 11: accept 010100100100100: accept 010000010010: reject : reject
Finite Automaton (def.) A deterministic finite automaton (DFA) M is defined by a 5-tuple M=(Q, , ,q0,F) Q: finite set of states : finite alphabet : transition function :Q Q q0 Q: start state F Q: set of accepting states
M = (Q, , ,q,F) 0 1 states Q = {q1,q2,q3} alphabet = {0,1} 1 0 q1 q2 q3 start state q1 accept states F={q2} transition function : 0,1 0 1 q q q 1 1 2 q q q 2 3 2 q q q 3 2 2
Recognizing Languages (def) A finite automaton M = (Q, , ,q,F) accepts a string/word w = w1 wn if and only if there is a sequence r0 rn of states in Q such that: 1) r0 = q0 2) (ri,wi+1) = ri+1for all i = 0, ,n 1 3) rn F
Regular Languages The language recognized by a finite automaton M is denoted by L(M). A regular language is a language for which there exists a recognizing finite automaton.
THT THANK YOU Prepared By:- Preeti Gupta Deptt. Of Computer Applications Prepared By:-PP
