Knowledge Point

  Long Answer Question Bank Theory of Automata & Formal Languages  UNIT 1 1.       Find closure of each state and give the set of all strings of length 3 or less accepted by automaton. 2.       Define DFA, NFA & Language? 3.       State and prove Myhill Nerode Theorm 4.       Design a DFA to accept string of 0’s & 1’s when interpreted as binary numbers would be multiple of 3 5.       Find closure of each state and give the set of all strings of length 3 or less accepted by automaton. 6.       Convert following NFA to DFA using subset construction method 7.       Write DFA to accept strings of 0’s, 1’s & 2’s beginning with a 0 followed by odd number of 1’s and ending with a 2. 8.       Construct DFA to accept the language of all strings of even numbers of a’s & numbers of b’s divisible by three over (a+b)*. 9.       Construct the minimum state automata for the following : Initial State :A Final S

  Video Lecture- https://www.youtube.com/watch?v=WuhG54DgIQ0

 1. How many tuples are in finite state machine? a) 3 b) 4 c) 5 d) infinite Answer-c Finite state machine is defined as 5-tuples (Q,∑,δ,q0,F) Where Q: finite set of states ∑: finite set of input symbol q0: initial state F: final state δ: Transition function 2. Which of the following is transition function for DFA . a) Q * Σ ->2^Q b) Q * Q -> Σ c) Σ * Σ -> Q d) Q * Σ -> Q Answer-d Explanation- The transition function for DFA is defined as δ: Q x ∑ →Q   3. How many states are required to accept string  which ends with 10. a) 3 b) 2 c) 1 d) 4 Answer:a 4. Which of the following is transition function for NDFA . a) Q * Σ ->2^Q b) Q * Q -> Σ c) Σ * Σ -> Q d) Q * Σ -> Q Answer-a The transition function for NDFA is defined as δ: Q x ∑ →2^Q   5. δ*(q1,xy) is equivalent to . a) δ((q1,y),x) b) δ(δ*(q1,x),y) c) δ(q1,xy) d) None of these Answer:b 6. String w is accepted by finite automata if . a) δ(q0,w)|-*qf b) δ(qf,w)|-*q0 c) δ(q0,qf)|-w d) δ(qf,q0)|-w Answer:a Explanation

 Mealy Machine – A mealy machine is defined as 6 tuples (Q, q0, ∑, Δ, δ, λ’)  Q - finite non empty set of states  q0 - initial state  ∑-  input alphabet or terminals  Δ - output alphabet  δ - transition function δ:Q×∑ → Q  λ - output function λ: Q×∑→ O  Moore Machine – A moore machine is defined as 6 tuples (Q, q0, ∑, Δ, δ, λ’)  Q - finite non empty set of states  q0 - initial state  ∑-  input alphabet or terminals  Δ - output alphabet  δ - transition function δ:Q×∑ → Q  λ - output function λ: Q→O  1. Moore Machine is : a) FA without input b) FA with output c) NDFA with input d) None of the above Answer: b Explanation: Finite automaton with an output is  categorized in two parts: Moore M/C and Mealy M/C. 2.Which of the following is uesd as  output alphabet  in moore machine? a) δ b) ∆ c) ∑ d) None of the above Answer-b 3.Which of the following produce output for moore machine?  a) λ: Q→O b) λ: Q×∑→ O c) both a and b d) none of the above 4.The Output of Moore machine depends on a) only

  Question: Answer each part for the following context-free grammar G. R → XRX | S S → aT b | bT a T → XT X | X | ε X → a | b very important : if you know how to answer these questions. leave your email and i will contact you or come here at 5 pm (new york time) you will answer similar questions. the point of asking this question is to be able to connect with someone who knows the topic a. What are the variables of G? b. What are the terminals of G? c. Which is the start variable of G? d. Give three strings in L(G). e. Give three strings not in L(G). f. True or False: T ⇒ aba. g. True or False: T ∗⇒ aba. h. True or False: T ⇒ T . i. True or False: T ∗⇒ T . j. True or False: XXX ∗⇒ aba. k. True or False: X ∗⇒ aba. l. True or False: T ∗⇒ XX. m. True or False: T ∗⇒ XXX. n. True or False: S ∗⇒ ε. o. Give a description in English of L(G). Answer Answer-a) Variables of grammar(G)-(R,X,S,T) Answer-b) Terminals of grammar(G)-{a,b} Answer-c) Starting variable of grammar(G)-{R} Answer-d) Three s

  Use the IDLE editor for a Python program with three functions: A function named square that accepts a number as an argument and returns the square of that number. (Remember, the square of a number is the number multiplied by itself. For example, 2 squared is 2 x 2 = 4.) A function named cube that accepts a number as an argument and returns the cube of that number. (Remember, the cube of a number is the number multiplied by itself twice. For example, 2 cubed is 2 x 2 x 2 = 8.) A main function that uses a loop to display the numbers from 1 to 10, and their squares, and their cubes. The output should be formatted as a table as shown below. The main function must call the square function and the cube function to calculate the square and cube of each number. The output must be printed from the main function with column headings as shown below. The numbers in the columns should be right-aligned. Answer- #function named square that accepts a number as an argument and returns the square of t

  Show that the language L = {aww R : w ∈ {a, b} * } is context-free. Answer- A language is context free language if it is generated by context free grammar. Therefore we generate grammar for given language. If grammar generated by language is context free grammar then given language will be context free language.  Explanation A language is context free language if it is generated by context free grammar. Therefore we generate grammar for given language. If grammar generated by language is context free grammar then given language will be context free language.  Language L = {aww R : w ∈ {a, b} * } is context-free. Grammar for language(L)- Grammar(G) = (V, Σ, P, S)  Where  V = {S,A} Σ = {a, b}, P = {  S→ aA , A → aAa , A → bAb , A →ε  } S={S} Starting symbol of grammar. Context free grammar- A grammar(G) is context free grammar if it is defined as G = (V, Σ, P, S) where  V= is a set of non-terminal symbols. Σ= is a set of terminals P= Production rule  P: V → (V ∪ Σ)* S=is the start symb

  Write the following functions and procedures in c ++ code. The function f1 that receives an integer value greater than or equal to one and using a for loop returns the result of the following summation: For example: The function f2 that receives an integer value greater than or equal to one and using a for loop returns the result of the following multiplication:  For example: The function f3 that receives an integer value greater than or equal to one and using a for loop returns the result of the following series: For example: The increment procedure receives 2 real parameters, the lower limit of the LI series and the upper limit of the LS series. And using a for loop, the procedure should display the sequence of numbers from LI to LS in 0.4 increments. For example: increment (3.0, 5.0), it will display on screen: 3.0, 3.4, 3.8, 4.2, 4.6, 5.0 increment (5.1, 7.2), it will display on screen: 5.1, 5.5, 5.9, 6.3, 6.7, 7.1 Answer-The function f1- #include <iostream> #include <cm