Theory of computation questions with solutions

Note remember page numbers

 c) bauab*a. ow the Regular Expression for the following FSM:

 

Q7. Given the following DFSM M, write a regular expression that describes —L(M):

 

Theory of computation important and basic questions easy way you can understand Consider the language l. = n > 0). Is the string 122 in L?

 

let Ll —- : n > O). Lct L2 = (cn : n > 0). For each of the following strings, state whether or not it is an element of L IL 2:

b) aabbcc.

c) abbcc.

d) aabbcccc.

Let L —— (w e (a, l)) • : lwlmod 3 = 0). List the first six elements in a lexicographic enumeration of L.

Give DFA's accepting the following languages over the alphabet (O, 1}.

i. The set of all strings-ending in 00.

2. The set of all strings with two consecutive o's (not necessarily at the end),

3. The set of strings with 011 as a substring.

5. Obtain a DFA to accept strings of a's and b's having even number of a's and b's Draw a DFA to accept string of o's and I's ending with the string 011

j. Write DFA to accept strings of 0'$, I's & 2's beginning with a 0 followed by odd number I's and ending with a 2.

Build a deterministic FSM for each of the following languages:

a) {w e (a, b) * : every a in w is immediately preceded and followed by b}.

b) {w E {a, b) * : w does not end in ba}.

c) (w e {0, 1) * : w corresponds to the binary encoding of natural numbers that are evenly divisible by 4}.

d) (w e {a, b) * : w has bbab as a substring}. 

or (aba)An where

Q5. Construct a DFA equivalent to the NFA: ({p, q, r, s), {O, 1}, , p, {q, s}), where '5' is given by:Q9. Consider the children's game Rock, Paper, Scissors . We'll say that the first player to win two rounds wins the game, Call the two players A and B.

a) Define an alphabet E and describe a technique for encoding Rock, Paper, Scissors games as strings over i. (Hint: each symbol in E should correspond to an ordered pair that describes the simultaneous actions of A and B.)

b) Let LRPS be the language of Rock, Paper, Scissors games, encoded as strings as described in part (a), that correspond to wins for player A. Show a DFSM that accepts LRPS.

  

h) {w e {a, b}* : w has both aa and bb as substrings}.

i) w has both aa and aba as substrings}.

j) w contains at least two b's that are not followed by an a}.

k) {w E {a, b}* : #a(w) E3 0}. #a(w) S 3}.

w contains exactly two occurrences of the substring aa}.

w contains no more than two occurrences of the substring aa}. every odd length string in L begins with 11}.

For each of the following statements, state whether it is True or False.

c) (a 

d)

e) (a 

f)

 

Q7. Construct NFA without E-transitions for the following NFA wg) If a and ß are any two regular expressions, then (a  = a(ßa ua).

h) If a and ß are any two regular expressions, then (aß)*a = a(ßa)* 

Q3. Let L = 

a) Show a regular expression for L.

b)Show an FSM that accepts L.

Q4. Convert each of the following regular expressions to an -NFA:

b) (0 + 1)01

 

Q5. Let L be the language accepted by the following finite state machine:

 

Indicate, for each of the following regular expressions, whether it correctly describes L:ithE-transitions.

 

Q Consider the DFA as shown in the following figure. Obtain the minimum state DFA

QIO. Show a deterministic FSM to accept each of the following languages. The point of this exercise is to see how much harder it is to build a deterministic FSM for tasks like these than it is to build an NDFSM. So do not simply built an NDFSM and then convert it. But do, after you build a DFSM, build an equivalent NDFSM.

a) {w e {a, b}* : the fourth from the last character is a}.

b) {w e {a, b} * : ax, y G {a, b}* : ((w =xabbaa y) V (w = x baba  

al. Write a regular expression to describe each of the following languages:

a) {w e {a, b} * : every a in w is immediately preceded and followed by b}.

b) {w E {a, b} * : w does not end in bal.

c) {w E {O, 1}* : w corresponds to the binary encoding, without leading O's, of natural numbers that are evenly divisible by 4}.

d) {w e {O, 1} * : w corresponds to the binary encoding, without leading O/s, of natural numbers that are powers of 4}.

 w has 001 as a substring). w does not have 001 as a substring}. {w e {a, . w has bba as a substring}.

 

 Q5. Consider the following NFA with E-transitions. Assume 'p' to be the initial state and 'r' as the final state.

1) Compute the E-closure of each state

2) List all the strings of length three or less accepted by the automata

3) Convert the automaton to its equivalent DFA