Sponsored Links


Results 1 to 1 of 1

Thread: cs402 subjective and objective mega file fall 2010 on 19-02-2011

  1. #1
    Administrator Xpert's Avatar
    Join Date
    May 2010
    Location
    Jhelum
    Posts
    6,239

    cs402 subjective and objective mega file fall 2010 on 19-02-2011

    Sponsored Links1


    It's the mega file which include all most all the mcq's, quiz and short question with subjective long questions and their answer's So please find the attachment for this.
    Q No 1.Give a example of converting a CFG to CNF?

    Consider the CFG given below
    S→ ABC
    A→ aa | b
    B→ c
    C→d
    Its CNF will be
    S→ DC
    D → AB
    A→ EE | b
    E→a
    B→c
    C→d
    Q No 2.In the lecture 41 's example, we have converted PDA to conversion form and a
    word 'aaaabb' is derived from this conversion form PDA. What are the derivation
    steps.
    The PDA converted to conversion form has some specific features that are important to
    understand first. These features are
    The states named START, READ, HERE and ACCEPT are called joints of the machine.
    With the help of the conversion form we have been able to achieve that POP state has only
    one path out of it and the path taking (multiple paths) decisions take place only on the READ
    state.
    The word 'aaaabb' is generated as follows from the PDA
    START-POP4-PUSH $
    This step pops $ and then pushes it to ensure that stack contains $ at the beginning.
    READ1-POP6-PUSH $-PUSH a
    As first time after reading "a" there is $ at the top of stack so we will follow path segment
    READ1-POP6-PUSH $-PUSH a
    READ1-POP5-PUSH a-PUSH a
    Now a is on the top of the stack so we will follow READ1-POP5-PUSH a-PUSH a
    READ1-POP5-PUSH a-PUSH a
    Again following same segment for a
    READ1-POP5-PUSH a-PUSH a
    Again following same segment for a
    READ1-POP1- HERE-POP2
    As we read b on input tape.
    READ2-POP1-HERE-POP2
    As we read b on input tape.
    READ2-POP3-ACCEPT.
    As we read Δ from the input tape
    Q No 3.How to differentiate between "wanted" and "unwanted branch" ?
    When we derive a word in Top down parsing beginning with the starting Non Terminal the
    branches of the tree that do not lead to our required word are left aside these branches are
    called unwanted branches.
    For example for CFG
    S----->AA
    A----->a | b
    If we want to generate the word "aa" we will leave the branch generated by the production A-
    ----->b.
    Q No 4.What is the difference between intersection and union of a language?
    Intersection of two languages will consist of all those words which are in both languages
    while union of two languages will consist of all those words which are present in at least one
    language.
    Symbol for intersection is ∩ and for union is U.
    Q No 5.What is the difference between Context free languages and regular
    languages?
    Regular languages can be represented by FA‟s because we do not need any memory to
    recognize (accept or reject them on FA) them but there is another class of languages that can
    not be represented by FA‟s because these languages require that we have some memory (with
    the help of memory we can store letters of the string we are checking so that we can compare
    them with next coming letters in the string).
    For example language anbn requires that we must store a‟s and then compare their count with
    next coming b‟s so that we can check whether a‟s are equal to b‟s or not.
    Due to this reason we use Context Free Grammars to represent them because we can5t write
    RE‟s for them.
    So Context Free Languages represent a broader category this category also include regular
    languages as subcategory. It means that context free languages include regular languages as
    well as some other languages.
    Q No 6.What is the difference between Moore and Mealey machines?
    In Mealy Machine we read input string letters and generate output while moving along
    the paths from one state to another while in Moore machine we generate output on
    reaching the state so the output pattern of Moore machine contains one extra letter
    because we generated output for state q0 where we read nothing.
    Q No 7.What does the following terms mean
    i. STACK Consistent
    ii. Y-able Paths
    iii. Working string
    iv. Semi Word means
    Stack consistence means that in the PDA converted in the conversion form, when we
    follow a path segment (which is formed by combining start, read or here state with
    next read, here or accept state on the path) along the PDA its pop state should have
    the path for the same letter that is present on the top of the stack at that stage. If this
    doesn‟t happen our PDA will crash because in conversion form of the PDA the pop
    state has only one letter path, so if we could not be able to find that letter on the top of
    the stack our PDA will crash (if will not find path where to go from that state)
    Working string means the string present on the input tape.
    Y-able Paths means that when we follow a certain sequence of rows from the row
    table to generate a path for a word form start state to accept state. The path (sequence
    of rows) should be stack as well as joint consistent it means that rows should end at
    the same read or here state (join consistency ) and the rows should be able to pop the
    letter from the top that is indicated in the pop state of the row.
    Semi word is the string of terminals it may be null string ending with a Non terminals
    on the right.
    For example some semi words are
    aaS
    aabbA
    B
    Question: Is Automata Theory is a Programming Subject or theoretical?
    Answer:
    Automata theory is the study of abstract computing devices, or "machines". This
    topic goes back to the days before digital computers and describes what is
    possible to compute using an abstract machine.
    These ideas directly apply to creating compilers, programming languages, and
    designing applications. They also provide a formal framework to analyze new
    types of computing devices, e.g. biocomputers or quantum computers
    Question: What are practical Examples of the implications of Automata Theory
    and the formal Languages?
    Answer:
    Grammars and languages are closely related to automata theory and
    are the basis of many important software components like:
    – Compilers and interpreters
    – Text editors and processors
    – Text searching
    – System verification
    Question: What are the Types of Automata?
    Answer: The Types of Automata Theory are
    1. Finite Automata
    2. Regular Languages
    3. Linear-bounded Automata
    4. Context Sensitive Languages
    5. Push-Down Automata
    6. Context Free Languages
    7. Turing Machines
    8. Recursively innumerable languages
    There are others as well like,
    Random Access Machines
    Parallel Random Access Machines
    Arrays of Automata
    Question: How types of Automata Differ?
    Answer: They differ in the following areas
    1. Complexity (or Simplicity)
    2. Power
    3. In the function that can be computed.
    4. In the languages that can be accepted.
    Question: What is the difference between the alphabet and an element of a set?
    Answer:
    Alphabets is a set of letters nothing else but a set of strings (elements) can have
    more than one letters in one string.
    Question: Difference between Palindrome and Reverse function?
    Answer: The language consisting of Λ and the strings s defined over Σ such that Rev(s)=s.
    It is to be denoted that the words of PALINDROME are called palindromes.
    Reverse (w) = w
    Example: Σ={a,b},
    PALINDROME={Λ , a, b, aa, bb, aaa, aba, bab, bbb, ...}
    If a is a word in some language L, then reverse (a) is the same string of letters spelled backwards,
    called the reverse of a.
    e.g
    reverse (xxx) = xxx
    reverse (623) = 326
    reverse (140) = 041
    Question: Define Strings?
    Answer: Concatenation of finite letters from the alphabet is called a string.
    e.g If Σ= {a,b} then a language L can be defined as
    L = {a, abab, aaabb, ababababababababab,...............}
    it's mean all words with a's more or equal to b's
    Question: Define empty or null strings?
    Answer: Concatenation of finite letters from the alphabet is called a string.
    Sometimes a string with no symbol at all is used, denoted by (Small Greek letter Lambda) λ
    or (Capital Greek letter Lambda) Λ, is called an empty string or null string.
    Question: Difference between string and word?
    Answer: Any combination of letters of alphabet that follows rules of language is called a word.
    A string is a finite sequence of symbols from an alphabet.
    Question: There are as many palindromes of length 2n as there are of length 2n-1, please explain?
    Answer: If we try to create palindromes then middle elements (2 in even palindromes & 1 in odd
    palindrome) does not cause any change in no. of palindromes
    Defining the language PALINDROME, of length 2n and 2n-1 defined over S = {a,b}
    e.g if we take n= 2 for 2n
    Length (2n) = 4 and string can be written as
    {aaaa, abba, baab, bbbb}
    And if we take n = 2 for 2n-1
    Length (2n-1) = 3 and string can be written as
    {aaa, aba, bab, bbb}
    Question: Define Kleene Star?
    Answer: Given Σ, then the Kleene Star Closure of the alphabet Σ, denoted by Σ*, is the collection of
    all strings defined over Σ, including Λ.
    It is to be noted that Kleene Star Closure can be defined over any set of strings.
    Examples
    If Σ = {x}
    Then Σ* = {Λ, x, xx, xxx, xxxx, ….}
    If Σ = {0,1}
    Then Σ* = {Λ, 0, 1, 00, 01, 10, 11, ….}
    If Σ = {aaB, c}
    Then Σ* = {Λ, aaB, c, aaBaaB, aaBc, caaB, cc, ….}
    Note:
    Languages generated by Kleene Star Closure of set of strings, are infinite languages. (By
    infinite language, it is supposed that the language contains infinite many words, each of finite
    length).
    Question: Why do not we can write" ba" in the set of PALINDROME while it is reverse of
    "ab".
    Answer: The language consisting of Λ and the strings s defined over Σ such that Rev(s)=s.
    It is to be denoted that the words of PALINDROME are called palindromes.
    Example
    For Σ={a,b},
    PALINDROME={Λ , a, b, aa, bb, aaa, aba, bab, bbb, ...}
    All two length string cannot satisfied the palindrome. aa and bb in palindrome but
    ba and ab are not in palindrome.
    Question: What are the steps of Recursive Definition of Languages?
    Answer: A recursive definition is characteristically a three-step process.
    First, we specify some basic objects in the set.
    Second, we give rules for constructing more objects in the set from ones we already know.
    Third, we declare that no objects except those constructed in this way are allowed in the set.
    Question: Strings that ending in "a " and strings containing exactly one "a".
    Answer: Its means all string ending in a
    e.g Σ= {a, b}
    {a, aa, ba, aba, baa,…….}
    Exactly a, defined over Σ= {a, b}
    {ab, ba, abb, bba,……... }
    Question: What is Lexical Analyzer?
    Answer: The first phase of the compiler is the lexical analyzer, also known as the scanner, which
    recognizes the basic language units, called tokens.
    • The exact characters in a token is called its lexeme.
    • Tokens are classified by token types, e.g. identifiers, constant literals, strings,
    operators, punctuation marks, and key words.
    • Different types of tokens may have their own semantic attributes (or values) which
    must be extracted and stored in the symbol table.
    • The lexical analyzer may perform semantic actions to extract such values and insert
    them in the symbol table.
    Question: What is accepting string language?
    Answer: The strings which follow rules for the language are accepted in language.
    • Let u and v be strings. Then uv denotes the string obtained by concatenating u with
    v, that is, uv is the string obtained by appending the sequence of symbols of v to that
    of u. For example if u = aab and v = bbab,
    then uv = aabbbab. Note that vu = bbabaab uv. We are going to use first few
    symbols of English alphabet such as a and b to denote symbols of an alphabet and
    those toward the end such as u and v for strings.
    Question: What is transition table?
    Answer: A complete transition table contains one column for each character. To save space,
    table compression may be used. Only non-error entries are explicitly represented in
    the table, using hashing, indirection or linked structures.
    Tabular representation of a function that takes two arguments and returns a value
    0 1

    Sponsored Links
    Attached Files Attached Files

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Replies: 0
    Last Post: 02-21-2011, 03:40 AM
  2. Replies: 0
    Last Post: 02-19-2011, 11:34 PM
  3. Replies: 0
    Last Post: 02-19-2011, 11:08 PM
  4. Replies: 0
    Last Post: 02-19-2011, 10:45 PM
  5. Replies: 0
    Last Post: 02-19-2011, 10:37 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
-: Vuhelp Disclaimer :-
None of the files shown here are hosted or transmitted by this server. The links are provided solely by this site's users. The administrator's or staff of Vuhelp.net cannot be held responsible for what its users post, or any other actions of its users. You may not use this site to distribute or download any material when you do not have the legal rights to do so. It is your own responsibility to adhere to these terms. If you have any doubts about legality of content or you have any suspicions, feel free to contact us.
Online Education | JhelumSoft