Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    Automata Theory Report

    Uploaded by

    arcillachristian01
    Automata theory

    Copyright:

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

    Automata Theory Report

    Uploaded by

    arcillachristian01
    2 views19 pages
    Automata theory

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Automata theory

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    2 views19 pages

    Automata Theory Report

    Uploaded by

    arcillachristian01
    Automata theory

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 19

    AUTOMATA

    THEORY
    is the study of abstract machines
    and the computational problems
    that can be solved using these
    machines. It is a branch of
    theoretical computer science and
    mathematics, focused on the
    definitions of mathematical
    models of computation and their
    applications.
    Automato
    n
    An abstract machine that
    processes inputs and
    transitions between
    different states according to
    predefined rules. There are
    several types of automata,
    each with varying
    computational power:
    Type's Of
    Automaton

    • Finite Automata (FA):


    Machines with a limited
    number of states, often
    used to model simple
    processes like lexical
    analysis in compilers.
    Type's Of
    Automaton

    • Pushdown Automata
    (PDA): Machines that
    include a stack as part of
    their memory, allowing
    them to recognize
    context-free languages,
    like those used in syntax
    analysis.
    Type's Of
    Automaton

    • Turing Machine (TM): The


    most powerful
    automaton, which can
    simulate any algorithm.
    It consists of an infinite
    tape and is used to
    model general
    computation.
    BASIC OF FORMAL
    LANGUAGES

    • Alphabet (Σ):An alphabet


    is a finite, non-empty set
    of symbols (also called
    characters or letters).
    For example, Σ = {a, b,
    c} is an alphabet
    containing three
    BASIC OF FORMAL
    LANGUAGES
    • String (Word):A string is a
    finite sequence of symbols
    from an alphabet. For
    instance, if Σ = {a, b},
    then "ab", "bba", and "aaa"
    are examples of strings
    over Σ.The empty string
    (denoted by ε) is a string
    BASIC OF FORMAL
    LANGUAGES
    • Language (L):A language is a
    set of strings over a given
    alphabet. A language can be
    finite or infinite.For example, if
    Σ = {a, b}, a language L could
    be L = {"ab", "aab", "bb"}.
    This is a finite language.An
    infinite language might be L =
    {a, aa, aaa, aaaa, ...}, which
    DIFFERENT LEVEL
    OF LANGUAGES
    •
    ANALYSIS
    Regular Languages (Type 3)- Can
    be recognized by deterministic or
    nondeterministic finite
    automata.Regular Grammar, which
    includes rules of the form:A → aB
    (where A, B are non-terminals, and
    a is a terminal symbol)A → a (where
    A is a non-terminal, and a is a
    terminal)
    EXAMPLE

    The language of all strings over


    the alphabet {0, 1} that
    contain an even number of 1s,
    which can be expressed by the
    regular expression: (0*10*1)*.
    DIFFERENT LEVEL
    OF LANGUAGES
    •
    ANALYSIS
    Context-Free Languages (Type 2)-
    Context-Free Grammar (CFG),
    where production rules are of the
    form:A → α (where A is a non-
    terminal, and α is any string of
    terminals and/or non-terminals).
    More expressive than regular
    languages, allowing the description
    of structures like nested or
    EXAMPLE

    The language of balanced


    parentheses L = { ( ^n ) ^n | n
    ≥ 0 }, where each open
    parenthesis is matched by a
    corresponding close
    parenthesis.
    DIFFERENT LEVEL
    OF LANGUAGES
    •
    ANALYSIS
    Context-Sensitive Languages (Type 1)-
    Context-Sensitive Grammar (CSG),
    where production rules are of the
    form:αAβ → αγβ (where A is a non-
    terminal, and α, β, γ are strings of
    terminals and/or non-terminals, with γ
    not being empty).Context-sensitive
    languages allow more complex
    structures where rules depend on the
    EXAMPLE

    The language {a^n b^n c^n | n


    ≥ 1}, where the number of a's,
    b's, and c's must be the same.
    DIFFERENT LEVEL
    OF LANGUAGES
    •
    ANALYSIS
    Recursively Enumerable Languages
    (Type 0)-Unrestricted Grammar, where
    production rules are of the form:α → β
    (where α and β are strings of terminals
    and non-terminals). Recursively
    enumerable languages are the most
    general class of languages in the
    hierarchy, recognized by Turing
    machines.
    EXAMPLE

    The language of all valid


    programs in a programming
    language (which can be
    recognized but not necessarily
    decided by a Turing machine).
    Summary: Chomsky Hierarchy and
    Language Automata
    Automaton Grammar
    Example
    Type Language

    Type 0:
    Unrestricted
    Recursively Turing Machine All valid programs
    Grammar
    Enumerable

    Type 1: Context- Linear Bounded Context-Sensitive


    `{a^n b^n c^n
    Sensitive Automaton Grammar

    Type 2: Context- Pushdown Context-Free Balanced


    Free Automaton Grammar parentheses

    Type 3: Regular Finite Automaton Regular Grammar Even number of 1s


    THANK YOU

    You might also like