Deterministic finite state machine

Assignment Help Theory of Computation
Reference no: EM13692991

EXERCISE 1: REGULAR EXPRESSIONS

Question 1. Let R1 = a((b*c*) + a)b and R2 = a* ((bc) + a*)b* be two regular expressions.

(a) Give two words ω1 and ω2 such that {ω1 ω2} ⊆ L(R1) ∩ L(R2). Please type each word on a new line.

(b) Give two words ω3 and ω4 such that (ω3, ω4) ⊆ L(R1) \ L(R2). Please type each word on a new line.

(c) Give two words ω5 and ω6 such that {ω5, ω6} ⊆ L(R2) \ L(R1). Please type each word on a new line.

(d) Give a regular expression R3 such that L(R3) = L(R1) U L(R2).

(e) Give a regular expression R4 such that L(R4) = L(R1) ∩ L(R2).

Question 2. Give regular expressions for the following languages.

(a) L1 = {anbm | n ≥ 3, m is even}.

(b) L2 = L1' (where L' stands for the complement of L).

(c) L3 = {abnω | n > 3, ω  ∈ {a, b}*}.

(d) L4 = {ωanω | n > 0, ω ∈ {a, b}*} ∩ {bωb | ∈ {a, c}*}.

Question 3. Let R1 and R2 be regular expressions over a non-empty alphabet E.

(a) Determine, formally, whether L(R1(R1 + R2)*) = L((R1 + R2)*). That is, if it is true, provide a proof; otherwise provide a counter example.

(b) Prove that L(R1R2)Τ = L(RΤ2, R2)*) where if represents the reverse of regular expression R. For example, if abb ∈ L(R), then bba L(R'). Similarly, if X is a set of words, then XΤ = {ω|ωr ∈ X}.

EXERCISE 2: GRAMMARS

Question 4. In this exercise, we use operator R# to denote one or more repetitions of R, that is, R# is a compact way of writing RR' (remember we used + for alternation). Let L1 and L2 be the following two languages over alphabet {a, b, c}:

L1 = {anb2cm a2+n+m | n,m ≥ 1};

L2 = L(((a + b)*b(b + (c + a) (b + a)* )#.

(a) Give a grammar G1 such that L(G1) = L1.

(b) Give a grammar G2 such that L(G2) = L2.

(c) Provide a grammar G3 such that L(G3) = L1 U L2.

(d) Prove formally that L1 ∩ L2 = L1

Question 5. Let G = ({S, A}, {a, b}, Γ, S) be a grammar, where the set of rules r is defined as follows:

S -> aSbS
S -> bSaS

S -> ∈

(a) Is G an ambiguous grammar? Explain your answer.

(b) Is there a relationship between the number of a's and b's in L(G)?

(c) Does there exist a regular expression R such that L(R) = L(G)? If it exists, provide such R; otherwise, briefly explain the reason for its nonexistence.

(d) Does there exist a regular expression, DFA, or PDA over the alphabet Σ = {a, b} which is equivalent to the language L1 = L(G) ∩ L(a*b*)? For each, briefly explain why not or provide the expression/automaton.

EXERCISE 3: AUTOMATA
Question 6. Answer the following questions based on the finite state automaton M1 present in the JFLAP file DFA-3.6.jff available in Course Material section of the course website.
 
(a) Give four strings of length 3 accepted by M1. Please type each string on a new line.
(b) Give four strings of length 3 rejected by M1. Please type each string on a new line.
(c) Do you think M1 has more states than required to express its language? Explain briefly.
(d) Give the language of this machine M1 as a regular expression.
(e) Create an automaton M2 such that it accepts the language L2 where L2 = L(M1) ∩ L(a*c*(c+ b)*). Your machine should not accept words not in this language.
 
Question 7. Let M3 = ({q0, q1, q2, q3}, {a, b} , δ, q0, {q3}) be a deterministic finite state machine as shown below. Prove that if w is a string in L(M3), then the number of a's in ω is na,(ω) mod 3 = O.

1919_AUTOMATA.png

Question 8. Consider the pushdown automaton M4 over the alphabet Σ = {a, b, c} as shown below.

2105_AUTOMATA1.png

Notation x, A/X means a transition where X is the input symbol being read, A is the symbol on top of the stack that is popped, and X is the symbol pushed onto the stack. The symbol ∈ stands for the "empty" string. Acceptance is by final state and empty stack.
 
(a) Give 4 strings of length 6 over Σ that are accepted by PDA M4.
(b) Give 4 strings of length 6 over Σ that are rejected by PDA M4.
(c) Give the language of M4 in set notation.
(d) Let M5 be a PDA obtained from M4 by removing the transitions δ(q4, ∈, ∈) = (q5, ∈), δ(q5, a, B) = (q5, ∈) and δ(q5, a, C) = (q5, ∈), adding transition δ(q4, a, B) = (q4, ∈), removing state q5 and making state q4 a final state. Give the language of M5 in set notation.

(e) Is there a relation between the language of M4 and M5. Explain briefly.

(f) It is a well known result that every PDA with acceptance condition of an empty stack and reachability of a final state can be transformed to an equivalent PDA with acceptance condition requiring only reachability of a final state. Transform the PDA M4 to an equivalent PDA with acceptance requiring only reachability of a final state.

Reference no: EM13692991

Questions Cloud

How long does the lighter skater take to reach the edge : Two ice skaters, with masses of 30kg and 85kg, are at the center of a 40m -diameter circular rink. how long does the lighter skater take to reach the edge
Obtain how far away from the edge of the pond is the person : An outdoor circular fish pond has a diameter of 4.00 m and a uniform full depth of 1.70m. How far away from the edge of the pond is the person
What is the flow speed in the constriction : Water flows through a 2.5cm -diameter pipe at 1.9m/s. If the pipe narrows to 1.5cm diameter,  What is the flow speed in the constriction
How much time would the observer have : An observer moving toward Earth with a speed of 0.95c notices that it takes 6.0 min for a person to fill her car with gas. How much time would the observer have measured for the car to be filled in this case
Deterministic finite state machine : Determine, formally, whether L(R1(R1 + R2)*) = L((R1 + R2)*). That is, if it is true, provide a proof; otherwise provide a counter example.It is a well known result that every PDA with acceptance condition of an empty stack and reachability of a fin..
What is the average power dissipated by a resistor : What is the average power dissipated by a resistor of resistance R = 25 ohm in an LRC circuit for which the power factor is equal to 0.25 and the maximum voltage of the AC source is 8 V
Determine the final image distance from second lens : Two lenses, one converging with focal length 21.5cm and one diverging with focal length 12.0cm, are placed 25.0cm apart. Find the final image distance from second lens. Follow the sign conventions
What is the total magnification : Two 24.1-cm-focal-length converging lenses are placed 16.5-cm apart. An object is placed 35.0-cm in front of one lens. What is the total magnification
Find how far from focal-length lens must an object be placed : How far from a 47.0-mm-focal-length lens must an object be placed if its image is to be magnified 1.50 x and be virtual

Reviews

Write a Review

Theory of Computation Questions & Answers

  Finite-state machine design

Create a finite-state machine design to turn your FPGA development board into a simple programmable music box.

  Redundant sequence identi cation

Redundant sequence identi cation

  Compute a shortest superstring

Dynamic programming algorithm to compute a shortest superstring.

  Propositional and predicate logic

Write down a structural induction principle for the PlayTree free type

  Design a syntactic analyzer

Design a syntactic analyzer for the language specified by the grammar

  Design unambiguous grammar to parse expressions

Write a program would read two numbers and then print all numbers between the first and the second, inclusive. Design unambiguous grammar to parse expressions

  Consider a logic function with three outputs

Consider a logic function with three outputs,  A ,  B , and  C , and three inputs,  D ,  E , and  F . The function is defined as follows:  A  is true if at least one input is true,  B  is true

  Considering a single programmed operating system

Considering a single programmed operating system, what is the minimal total time required to complete executions of the two processes? You should explain your answer with a diagram.

  How to construct an nfa

Give a construction that assumes you are given a DFA for L and show how to construct an NFA (with or without ε-moves) to recognize sort(L).

  Equivalence classes to construct minimal dfa for language

How many equivalence classes does this relation have and what are they? Use these equivalence classes to construct the minimal DFA for the language.

  Impact of moore-s law on data center costs

Discuss the impact of Moore's law on data center costs on such things as servers and communications equipment. List at least 3 steps or recommendations your data center can take to offset some or all of the effect of Moore's law.

  Problem encountered in statements in predicate logic

How the problem would be encountered in attempting to represent the following statements in Predicate logic. it should be possible to: John only likes to see French movies.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd