Scribd Logo
Upload

Welcome to Scribd!

  • 27 views

    Formal Languages Models of Computation: Spring 2005 Costas Busch - RPI

    Uploaded by

    paksmiler
    The document describes models of computation including formal languages, automata, and Turing machines. It defines different types of automata based on their temporary memory, including finite automata with no memory, pushdown automata with a stack, and Turing machines with random access memory. Strings and languages are defined as sets of strings over an alphabet. Common operations on strings and languages are described such as concatenation, reversal, and Kleene closure. Examples are provided to illustrate concepts such as substrings, prefixes, suffixes, and language operations.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Formal Languages Models of Computation: Spring 2005 Costas Busch - RPI

    Uploaded by

    paksmiler
    27 views36 pages
    The document describes models of computation including formal languages, automata, and Turing machines. It defines different types of automata based on their temporary memory, including finite automata with no memory, pushdown automata with a stack, and Turing machines with random access memory. Strings and languages are defined as sets of strings over an alphabet. Common operations on strings and languages are described such as concatenation, reversal, and Kleene closure. Examples are provided to illustrate concepts such as substrings, prefixes, suffixes, and language operations.

    Original Title

    azclass0.ppt

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes models of computation including formal languages, automata, and Turing machines. It defines different types of automata based on their temporary memory, including finite automata with no memory, pushdown automata with a stack, and Turing machines with random access memory. Strings and languages are defined as sets of strings over an alphabet. Common operations on strings and languages are described such as concatenation, reversal, and Kleene closure. Examples are provided to illustrate concepts such as substrings, prefixes, suffixes, and language operations.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    27 views36 pages

    Formal Languages Models of Computation: Spring 2005 Costas Busch - RPI

    Uploaded by

    paksmiler
    The document describes models of computation including formal languages, automata, and Turing machines. It defines different types of automata based on their temporary memory, including finite automata with no memory, pushdown automata with a stack, and Turing machines with random access memory. Strings and languages are defined as sets of strings over an alphabet. Common operations on strings and languages are described such as concatenation, reversal, and Kleene closure. Examples are provided to illustrate concepts such as substrings, prefixes, suffixes, and language operations.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 36

    Formal Languages

    Models of Computation

    Computation

    CPU

    memory

    temporary memory
    input memory
    CPU
    output memory
    Program memory

    Example:

    f ( x) x

    temporary memory
    input memory
    CPU
    output memory

    Program memory
    compute
    compute

    xx
    2

    x x

    f ( x) x
    temporary memory

    input memory

    x2
    CPU
    output memory

    Program memory
    compute
    compute

    xx
    2

    x x

    temporary memory

    z 2*2 4
    f ( x) z * 2 8

    f ( x) x

    input memory

    x2
    CPU
    output memory

    Program memory
    compute
    compute

    xx
    2

    x x

    temporary memory

    z 2*2 4
    f ( x) z * 2 8

    f ( x) x

    input memory

    x2
    CPU
    Program memory
    compute
    compute

    xx
    2

    x x

    f ( x) 8
    output memory

    Automaton
    temporary memory
    Automaton

    input memory
    CPU
    output memory

    Program memory

    Different Kinds of Automata


    Automata are distinguished by the temporary memory
    Finite Automata:

    no temporary memory

    Pushdown Automata:

    stack

    Turing Machines:

    random access memory

    Finite Automaton
    temporary memory

    Finite
    Automaton

    Example: Vending Machines


    (small computing power)

    input memory
    output memory

    Pushdown Automaton
    Stack

    Pushdown
    Automaton

    Push, Pop

    input memory
    output memory

    Example: Compilers for Programming Languages


    (medium computing power)

    Turing Machine
    Random Access Memory

    Turing
    Machine

    input memory
    output memory

    Examples: Any Algorithm


    (highest computing power)

    Power of Automata

    Finite

    Pushdown

    Turing

    Automata

    Automata

    Machine

    Less power

    More power
    Solve more
    computational problems

    Languages

    A language is a set of strings


    String: A sequence of letters
    Examples: cat, dog, house,
    Defined over an alphabet:

    a, b, c, , z

    Alphabets and Strings


    We will use small alphabets:
    Strings

    a
    ab
    abba
    baba
    aaabbbaabab

    a, b

    u ab
    v bbbaaa
    w abba

    String Operations

    w a1a2 an

    abba
    bbbaaa

    v b1b2 bm
    Concatenation

    wv a1a2 anb1b2 bm

    abbabbbaaa

    w a1a2 an

    ababaaabbb

    Reverse
    R

    w an a2 a1

    bbbaaababa

    String Length

    w a1a2 an
    Length:

    Examples:

    w n
    abba 4
    aa 2
    a 1

    Length of Concatenation

    uv u v
    Example:

    u aab, u 3
    v abaab, v 5
    uv aababaab 8
    uv u v 3 5 8

    Empty String
    A string with no letters:

    Observations:

    0
    w w w
    abba abba abba

    Substring
    Substring of string:
    a subsequence of consecutive characters
    String

    Substring

    abbab
    abbab
    abbab
    abbab

    ab
    abba
    b
    bbab

    Prefix and Suffix

    abbab
    Prefixes

    Suffixes

    a
    ab
    abb
    abba
    abbab

    abbab
    bbab
    bab
    ab
    b

    w uv
    prefix
    suffix

    Another Operation
    n

    w ww

    w
    n

    Example:

    Definition:

    abba abbaabba
    2

    abba
    0

    The * Operation

    * : the set of all possible strings from


    alphabet
    a, b
    * , a, b, aa, ab, ba, bb, aaa, aab,

    The + Operation

    : the set of all possible strings from

    alphabet except

    a, b
    * , a, b, aa, ab, ba, bb, aaa, aab,

    a, b, aa, ab, ba, bb, aaa, aab,

    Languages
    A language is any subset of

    Example:

    a, b
    * , a, b, aa, ab, ba, bb, aaa,

    Languages:


    a, aa, aab
    { , abba, baba, aa, ab, aaaaaa}

    Note that:
    Sets

    { } {}

    Set size

    {} 0

    Set size

    {} 1

    String length

    Another Example
    An infinite language

    ab
    aabb
    aaaaabbbbb

    n n

    L {a b : n 0}

    abb L

    Operations on Languages
    The usual set operations

    a, ab, aaaa bb, ab {a, ab, bb, aaaa}


    a, ab, aaaa bb, ab {ab}
    a, ab, aaaa bb, ab a, aaaa
    Complement:

    L * L

    a, ba , b, aa, ab, bb, aaa,

    Reverse
    Definition:
    Examples:

    L {w : w L}

    ab, aab, baba ba, baa, abab


    R

    n n

    L {a b : n 0}
    R

    n n

    L {b a : n 0}

    Concatenation
    Definition:

    Example:

    L1L2 xy : x L1, y L2

    a, ab, ba b, aa
    ab, aaa, abb, abaa, bab, baaa

    Another Operation
    Definition:

    L LL L
    n

    a, b a, b a, b a, b
    aaa, aab, aba, abb, baa, bab, bba, bbb
    3

    Special case: L

    a , bba , aaa 0

    More Examples
    n n

    L {a b : n 0}
    2

    n n m m

    L {a b a b : n, m 0}
    2

    aabbaaabbb L

    Star-Closure (Kleene *)
    Definition:

    Example:

    L* L L L

    a, bb,

    a, bb *

    aa
    ,
    abb
    ,
    bba
    ,
    bbbb
    ,

    aaa, aabb, abba, abbbb,

    Positive Closure
    Definition:

    L L L
    L *

    a, bb,


    a, bb aa, abb, bba, bbbb,

    aaa, aabb, abba, abbbb,

    You might also like