EXAMSHARE

Western Delta University, Oghara Delta State

department of computer science
college of computing
western delta university

first semester examination 2023/2024 session

CSC307 - formal language and automata theory time: 2hrs: 30mins

Attempt question one (1) and any other three (3) questions

  1. Question 1 (Compulsory) (25 marks)

    1. Define the following:
      1. Automation
      2. Automata Theory
      3. Alphabets
      4. Strings
      5. Language
      6. Empty String
      (6 marks)
      1. State the objective of Automata Theory (2 marks)
      2. Using suitable diagrams only, represent Automation and its configuration. (4 marks)
      1. Consider the string "q r s t u v w x y z". Determine the length of the string. (2 marks)
      2. If x = "a b c d e f g h" and y = "m n o p q r st", compute the concatenation of xy. (2 marks)
      3. Given that w = 10111101011010001110. Find (w)R. (2 marks)
      1. Give a formal description of Context Free Grammer (CFG). Assume that the production rule for a regular expression is as follows:
        S -> bS..................Rule 1
        S -> e...................Rule 2
        (3 marks)
      2. Derive the string "bbbbbb" (4 marks)

  2. Question 2 (15 marks)

      1. Define Derivation and Parse Tree. (2 marks)
      2. List and explain two (2) types of derivation. (3 marks)
    2. Write down four (4) properties of a parse tree. (4 marks)
    3. Consider the Grammer:
      S -> aAS/aSS/e..................Rule 1
      A -> SbA/ba.....................Rule 2
      1. Using leftmost derivation, derive the string "aabaa"(3 marks)
      2. Show the corresponding parse treee. (3 marks)

  3. Question 3 (15 marks)

    1. Define the following:
      1. Rightmost Derivation
      2. Rightmost Derivation Tree
        3. (4 marks)
    2. Context Free Grammers (CFG) are recognized by what automation? (2 marks)
    3. The production rule for a regular expression is given as follows:
      S -> AB/e..................Rule 1
      A -> aB....................Rule 2
      B -> Sb....................Rule 3
      1. Derive the string "abb"(5 marks)
      2. Draw the parse tree (4 marks)

  4. Question 4 (15 marks)

    1. Write a formal definition of finite automata. (3 marks)
    2. Write explanatory notes on transition diagram and transition table. (4 marks)
    3. Construct a Deterministic Finite Automata (DFA) accepting all strings over {x, y} ending with 'xy' using the following procedure:
      1. Develop a Mathematical Model. (2 marks)
      2. Generate the transition diagram. (3 marks)
      3. Draw the corresponding transition table. (3 marks)

  5. Question 5 (15 marks)

    1. Why is Push Down Automata (PDA) more powerful than a Finite State Machine (FSM). State the three (3) components of a Push Down Automata. (4 marks)
    2. With the aid of a diagram only, illustrate the working principle of a Push Down Automata (PDA). (3 marks)
    3. Construct a push down automata that accepts L = {ikjk for k = 3}. Use the following steps:
      1. Draft a Mathematical Model. (2 marks)
      2. Show the contents of the stack for each iteration. (3 marks)
      3. Draw the transition diagram. (3 marks)

  6. Question 6 (15 marks)

    1. A Turing machine has what data structure? Highlight four (4) rules of Operation of Turing machines. (5 marks)
    2. List and explain five (5) applications of Turing machines. (5 marks)
    3. Design a Turing machine which recognizes the language L = 01*0 (5 marks)