Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    ALC Assignment I 2024

    Uploaded by

    hosecej277
    Auto language computation

    Copyright:

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

    ALC Assignment I 2024

    Uploaded by

    hosecej277
    4 views4 pages
    Auto language computation

    Original Title

    ALC_Assignment_I_2024

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Auto language computation

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    4 views4 pages

    ALC Assignment I 2024

    Uploaded by

    hosecej277
    Auto language computation

    Copyright:

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

    NAWAB SHAH ALAM KHAN COLLEGE OF ENGINEERING & TECHNOLOGY

    (Approved by AICTE|Affiliated to Osmania University) (Autonomous)


    B.E. II Yr. III_Sem_ALC_Assginment #01

    ALC_Submission Due:13th Sep’24 [10 Marks] Branch: CSE_AIML

     Please follow the College Instructions. Don’t forget to write your Name & ID#.
     · Be Self-Seeking · You are requested to Answer all Questions. Answers in
    English only ·
    Grades will be depending on – Clarity, Creativity & Innovative …

    SAQs

    Q#1)

    a) Define FA & Differentiate NFA Vs DFA. Write examples.

    b) What is Є-closure of a state S0? Explain with example.


    +
    c) Define the Languages the Kleene closure L* and Positive Closure L with examples.
    +
    d) T = {a, ab, b} and G = {ab, ba}. List the elements of GT and the elements of TG, T* & T
    e) A = {a, bb}. Write the elements of A2 and A3 .
    f) Define Regular Language & Expression. (01)* represents the language L=?

    LAQs

    Q#2)a) Draw a state diagram for a finite automaton that recognizes all strings
    over {a, b} that contain the substring ‘ aaa’.

    b) Q = { 0, 1 }, ∑= { a, b }, A = { 0 }, the initial state is 0 and is as shown in the


    following transition table.

    By Syed Mutiullah Hussaini Sr.Faculty Member MCA_CSE_IT_DS_IoT@NSAKCET _Hyd 1


    A state transition diagram for this DFA is as ________________

    c) For the following Transition Table Draw a Transition State Diagram:

    Present State Next state for Input a Next State of Input b

    →S0 S0 S1

    S1 S2 S1

    *S2 S2 S2

    d) Design a NFA for the transition table as given below:

    Present State a b

    →q0 q0, q1 q0, q2

    q1 q3 ε

    q2 q2, q3 q3

    *q3 q3 q3

    By Syed Mutiullah Hussaini Sr.Faculty Member MCA_CSE_IT_DS_IoT@NSAKCET _Hyd 2


    Q#3)

    a) Design FA with ∑ = {a, b} accepts the set of all strings with three
    consecutive a's.

    b) Design a FA with ∑ = {0, 1} accepts the strings with an even number


    of 1's followed by single 0.

    c) DFA with ∑ = {a, b} accepts all ending with a.

    d) Design a NFA from given regular expression 1 (1* 01* 01*)*.

    Q#4)

    a) Construct a CFG for a language L = {wcwR | where w € (a, b)*}.

    The string that can be generated for a given language is

    {aacaa, bcb, abcba, bacab, abbcbba, ....} & derive a string "abbcbba"

    The grammar could be:

    1. S → aSa rule 1
    2. S → bSb rule 2
    3. S → c rule 3

    b) Derive the string "abb" for leftmost derivation and rightmost


    derivation using a CFG given by,

    1. S → AB | ε
    2. A → aB
    3. B → Sb

    c) Derive the string "aabbabba" for leftmost derivation and rightmost


    derivation using a CFG given by,

    1. S → aB | bA
    2. S → a | aS | bAA
    By Syed Mutiullah Hussaini Sr.Faculty Member MCA_CSE_IT_DS_IoT@NSAKCET _Hyd 3
    3. S → b | aS | aBB

    d) Draw a derivation tree for the string "bab" from the CFG given by

    1. S → bSb | a | b
    e) Check whether the given grammar G is ambiguous or not.
    1. A → AA
    2. A → (A)
    3. A → a
    For the string "a(a)aa" the above grammar can generate two parse
    trees:

    ***Good Luck***

    By Syed Mutiullah Hussaini Sr.Faculty Member MCA_CSE_IT_DS_IoT@NSAKCET _Hyd 4

    You might also like