[CE 160 homepage]

CE 160 Automata and Formal Languages
Some Exam Questions from First Semester, 2002-2003

• Construct graphically a finite automaton equivalent to the regular expression: (10)*+[(0+11)0*1]*. The automaton may be nondeterministic with e-moves.
  
  
• Consider the following claim:
  For every NFA with e-moves, having two or more final states, there is an equivalent NFA with e-moves with exactly one final state.
  
  • Explain how the equivalent NFA could be constructed graphically, given the graph of the NFA having two or more final states.
    
  • Let M=(Q,S,d,A,F) be an NFA with e-moves with |F| >= 2. Construct formally the equivalent NFA with e-moves M'=(Q',S,d',A',F'), with exactly one final state, by specifying Q', d', A', F' in relation to M=(Q,S,d,A,F).
    
    
• Construct graphically an NFA that accepts the language described as the set of all strings over {0,1}such that the 10th symbol from the right end is 1.
  
  
• Let S = {0,1}and let L be a finite subset of S*. Explain why L is regular.
  
  
• Let L = {0ⁱ1^j0^i+j | i >=1 and j >= 1}, a subset of {0,1}*. Use the pumping lemma for regular sets to show that L is not regular.
  
  
• Let L be the set of all strings in {0,1}* that DO NOT have three consecutive 0's. Construct graphically a DFA accepting L.
  
  
• Recall that the equivalence relation R_L associated with a language is defined as follows:
  if and are strings, then x R_L y if and only if for each string z, either both or neither of xz and yz are in L.
  
  Let L = {x | x is in {0,1}* and x = x^R }where x^R is x written backward; for example, (011)^R = 110.
  
  
  1. Identify an infinite set S, of strings in {0,1}* such that any two strings in S belong to different equivalence classes induced by R_L. Explain briefly why the strings in S belong to different equivalence classes of L.
     
     
  2. Why can it be concluded from part (a) that L is nonregular?
     
     
• Let M = ( {a,b,c,d,e,f}, {0,1}, d, a, {a,c} ) be a DFA with d defined by the following table:

  	0	1
  a	b	d
  b	e	c
  c	b	f
  d	a	e
  e	e	e
  f	c	e

Find a minimum state DFA equivalent to M.

• Let G be the grammar
  

  S		aB|bA
  A		a|aS|bAA
  B		b|bS|aBB

  Draw a parse tree for aaabbabbba.

• Let G = (V,T,P,S) be a CFG whose productions are all of the form AaB or Aa where A and B are variables and a is a terminal.
  
  
  1. Illustrate how a parse tree for a string in L(G) looks.
     
  2. If w is in L(G), what is the length, in terms of |w|, of the longest path, from the root S to a terminal, in a parse tree for w?
     
  3. At least how long must a string w in L(G) be for the parse tree of w to have a path, from S to a terminal, with at least internal |V|+1 internal nodes (labelled by elements of V) ?
     
     
  4. Develop a stronger version of the pumping lemma for CFL's valid for grammars of the form described above.
     

This page has been accessed

times since June 25, 2002.