Two marks Questions with Answers

Two Marks Questions with Answers

Q.1 Is it true that the language accepted by any NFA is different from the regular language? Justify your answer. AU: May-04

Ans. No, any language accepted by DFA, NFA, ε-NFA is called a regular language. For any finite automaton we can construct an equivalent regular expression and the language represented by regular expressions is a regular language.

Q.2 Describe the following by regular expression

a) L1 = The set of all strings of 0's and 1's ending in 00.

b) L2 The set of all strings of 0's and 1's beginning with 0 and ending with 1.

AU: May-04, Dec.-12

Ans. a) The set of all strings of 0's and 1's is given by (0 + 1)*.

Hence r.e. for L₁ = (0+1)^* 00.

b) The set of all strings beginning with 0 can be 0 (0+1)*.

Hence r.e. for L2 = 0 (0+1)* 1.

Q.3 Show that (r^*)^* = r^* for a regular expression r. AU: Dec.-04

Ans. Consider,

r = 0     where Σ = {0}

Now   L.H.S. = (r*)*

= ((0)*)*

= {ε, 0, 00, 000, ...}  …(1)

Thus the set contains string of O's including null string.

Now R.H.S. = r*

= (0)*

= {ε, 0, 00, ... } …(2)

From equation (1) and (2) it is proved that

L.H.S. = R.H.S.

Hence,   (r*)* = r

Q.4 Find the language accepted by the following automaton. AU : May-05

Ans. The r.e. that can be obtained from given DFA is

r.e. = 0* 1*

That means the strings accepted by FA will be any number of O's followed by any number of 1's. Any number means it can be zero as well.

Q.5 Define regular expression. Give an example. AU: Dec.-05, May-13

Ans. Let Σ be an alphabet which is used to denote the input set. The regular expression over Σ can be defined as follows.

1. ϕ is a regular expression which denotes the empty set.

2. ε is a regular expression and denotes the set {ε}.

3. For each 'a' in Σ 'a' is a regular expression that denotes the set {a}.

4. If r and s are regular expressions denoting the languages L1 and L2 respectively then

r+s is equivalent to L₁ U L₂ i.e. union.

rs is equivalent to L₁ L₂ i.e. concatenation.

r^* is equivalent to L₁^* such that if Σ = {a} then

L₁^* = {ε, a, aa, ...}

For example: Write the regular expression for the language accepting all possible string over = {a}.

Regular expression = a^*

Q.6 Let R be any set of regular languages. Is U R_j regular? Prove it. AU: Dec.-06

Ans. If R be the set of regular languages then U R is regular.

Proof : Let, r = r₁ + r₂ where r₁ and r₂ be the regular expressions.

There exists two NFA's.

M₁ = (Q₁, Σ₁, δ₁, {f₁})

M₁ = (Q₂, Σ₂, δ₂, {f₂})

L(M₁) = L(r₁): Means the language stated by r₁ is same which is represented by M₁. Similarly L(M₂) = L(r₂).

Q₁ represents the set of all the states in machine M₁.

Q₂ represents the set of all the states in machine M₂.

It can be represented as,

We assume that Q₁ and Q₂ are totally disjoint. We will now assume q₀ as a new initial state and f₀ be the new final state. Then we will form new machine M as

M = ((Q₁ U Q₂ U {q₀, f₀}), (Σ₁ U Σ₂), δ, q₀{f₀})

This shows that L(M) = L(M₁) U L(M₂)

i.e. L(R) = L(r) = L(r₁) U L(r₂)

The machine designed for L(r₁) U L(r₂) shows that language R_i is regular.

Q.7 Verify whether L = {a²ⁿ |n ≥1} is regular. AU: May-07

Ans. Refer similar example 2.6.2.

Q.8 State pumping lemma and its advantages. AU: Nov.-14, Dec.-07, 08, 13, 17

Ans.: Pumping lemma: Let L be a regular set. Then there exists a constant n such that if z is any word in L such that |z| ≥ n then we can write z = uvw such that |uv| <n and |v| ≥ 1 for all i ≥ 0 and uv¹w is in L. The n indicates number of states in FA and should not be greater than the number of states.

The advantage of pumping lemma is that this theorem is used to check whether given language is regular or not.

Q.9 Show that the complement of a regular language is also regular. AU: Dec.-07

Ans. If L is a regular language, then its complement denoted by L' is also regular. To prove this, consider that language L is accepted by finite automaton M. Now all the words accepted by language L will reach to final state of machine M. If we change all the states of M to non-final states and all the non-final states of M to final state we get a new FA which is denoted by M'. Now this M' will accept all the words not belonging to L and reject all the words belonging to L. That means M' will accept the language L'. Thus there exists FA which accepts L'. Hence L' which is complement of L is also regular.

Q.10 Construct a DFA for the regular expression aa^*bb^*. AU : May-08

Ans. The DFA for aa*bb* is -

The state q₀ is a start state and state q₂ is a final state.

Q.11 Show that the complement of regular language is also regular. AU: Dec:-08

Ans. Refer answer of Q.9

If L is a regular language, then its complement denoted by L' is also regular. To prove this, consider that language L is accepted by finite automaton M. Now all the words accepted by language L will reach to final state of machine M. If we change all the states of M to non-final states and all the non-final states of M to final state we get a new FA which is denoted by M'. Now this M' will accept all the words not belonging to L and reject all the words belonging to L. That means M' will accept the language L'. Thus there exists FA which accepts L'. Hence L' which is complement of L is also regular.

Q.12 Show that ϕ is ϵ by constructing its NFA using Thomson's construction. AU: Dec.-08

Ans. The Thomson's construction for ϕ^* will be

Note that is represented by q₁ to f₁. We can reach to a final state f₀ from q₀ with input ε. Hence ϕ^* = ε is shown by above figure.

Q.13 Construct an NDFA for all strings over alphabet = {a, b} that contains a substring 'ab'. AU: May-09

Ans. The NDFA over Σ = (a, b) is -

The transition table will be

Q.14 Write regular expressions for the following language over the alphabet Σ = {0,1}. "The set of all strings not containing 101 as a substring". Provide justification that your regular expression is correct. AU : May-09

Ans. We will first construct DFA for the language containing 101 as substring.

Now, just change the non-final states to final states and make final state as non-final state. The DFA then becomes –

The regular expression for above DFA will be

r.e. = 0^*(1^*(00^*)^*)^*

Q.15 Prove or disprove the following for regular expression (a+b) + (cd) for Σ = {a,b,c,d}. AU: May-09

Ans.: To prove whether or not given language is regular or not following theorem is used -

"For every regular language there exists a finite automata".

If we could be able to build the FA for given expression then that expression is side to be regular. Hence

The NFA with ε can be built for given expression.

Hence the given expression is regular.

Q.16 What is [10,11]^* ? (Write atleast first seven terms). AU: Dec.-09

Ans.: The {10+ 11}^* is a set containing the strings of any combination of 10 and 11. This set also contains & or null string.

The items of this set are

{ε, 10, 11, 1010, 1011, 1111, 1110, 111111, 101010, ...}

Q.17 Let L= {W: W ϵ {0, 1}^* W does not contain 00 and is not empty}. Construct a regular expression that generates L} AU : May-10

Ans: We will first build a finite automata for the language accepting the strings containing 00.

Now to accept the language which does not contain 00, we will change the non final state to final state and final state to non final state.

The regular expression will be (01+ 1) + (10+ 1) + 0.

Q.18 Is the set of strings over the alphabet {0} of the form 0ⁿ where n is not a prime is regular ? Prove or disprove. AU: Dec.-11

Ans. Let us assume that L is a regular language n is not a prime number.

Let zϵL, L = 0ⁿ

|z| = uvw,     here i = 1.

Now consider L = uvⁱ w     where i = 2

= u v. vw

That means adding 1 to n, we get

n < |uvvw|

n < n+1

But (n + 1) can be a prime number. Hence our assumption becomes contradictory to it. This shows that L is not regular language.

Q.19 Construct regular expression for the language over the set ẑ = {a,b} in which total number of a's are divisible by 3.

Ans. r.e. = (b* ab* ab* a)*

Q.20 Find out the language generated by the regular expression (0+1)*.

Ans.: L = {ε, 0, 1, 00, 11, 01, 10,111, ....}

L = {Any number of 0's and 1's including nullstring}

Q.21 What is the closure property of regular set s?

Ans.: If certain languages are regular and language L is formed by them by certain operations such as (union, concatenation and so on) and if we find L as regular, then this property is called closure property of regular sets.

Q.22 Mention the applications of pumping lemma.

Ans.: 1. Pumping lemma is used for deciding whether or not the given language is regular.

2. It is also useful for determing whether L is accepted by a regular expression or not.

Example 1:

L = {0ⁿ1ⁿ} is not regular.

L = {0^P|p-is a prime number}

Example 2:

All these languages are non-regular languages and this can be proved by pumping lemma.

Q.23 Is it true that the language accepted by NFA is different from regular language? Justify your answer.

Ans. The language accepted by NFA is always regular. Because any NFA is equivalent to DFA. And if we represent certain language by NFA then we can definitely represent it using DFA. The regular language is a kind of language which can be represented by DFA. Hence the language accepted by NFA is not different from regular language.

Q.24 Give regular expression to describe an identifier and positive integer.

Ans.: id = (a - zA - Z) (a - zA - Z 0-9)^*

P = (0-9)⁺

Q.25 Find the string of minimum length in {0,1}* NOT in the language corresponding to the given regular expressions.

a) 0* (100*) * 1*            b) (1+01) (0 +01) *

Ans. a) {110} € 0* (100*)* 1*.

b) ϕ.

Q.26 Design FA that accepts {0,1}^*.

Ans.:

Q.27 Write a regular expression which generates strings with at least one 0 and one 1.

Ans. r.e. = = (0⁺ 1*) (1⁺ 0*) (0+1)*

Q.28 Give the operations that satisfy closure properties of regular languages.

Ans. The operations are union, intersection, complement, difference, reversal, concatenation, reversal, homomorphism, inverse homomorphism.

Q.29 Give a regular expression for the set of all strings having odd number of 1's.

Ans.: r.e. = 1(0+11)*

Q.30 State the precedence of regular expression operators.

Ans.:

1. The star operator is having highest precedence.

2. The dot operator (concatenation) has the next highest position,

3. Final precedence is given to + i.e. union operation. The union is an associative operator.

Q.31 What does regular expression (a/b) * denote ?

Ans. The strings generated by the given expression are {ε, a, b, aa, bb, ab, ba, ....} This denotes the language L = {Any number of a's and/or b's including null string}.

Q.32 Give the regular expression for set of all strings ending in 00. AU: Dec.-10

Ans. r.e. = = (0+1)^* 00

Q.33 Construct NFA for regular expression a*b*. AU: May-12

Ans.:

Q.34 Is regular set closed under complementation? Justify. AU : May-12

Ans. Yes regular set is closed under complementation. The regular set is denoted by the regular languages and regular languages are closed under complementation. Refer answer of Q.9.

Q.35 Differentiate regular expression and regular language. AU : Dec.-12

Ans.

Regular expression over Σ can be defined by the operations such as r+s, rs and r* where r^* and s both are regular expressions. The regular languages over Σ is defined as -

1. An empty set ϕ.

3. L₁ U L₂ are regular languages.

2. L₁ L₂ are regular languages.

4. L₁^* is regular language.

The regular language is elaboration of regular expression. The regular expression denotes the tiny logical unit. It is typically used to represent pattern.

Q.36 Name any four closure properties of regular languages. AU: May-13

Ans.:

1. The union of two regular languages is regular.

2. The intersection of two regular languages is regular.

3. The complement of regular language is regular.

4. The closure operation on a regular languages is regular.

Q.37 Construct NFA equivalent to the regular expression (0 + 1) 0 1. AU: Dec.-13

Ans. :

Q.38 What is meant by equivalent states in DFA ? AU: Dec.-07

Ans. The two states are said to be equivalent if there are same inputs coming to the state and same output going out from the states.

Q.39 Construct a finite automation for the regular expression 0*1*.

Ans. :

Q.40 Prove or disprove that (r+s)* = r* +s*.

Ans.:

Note that in R.H.S. there is no combination of r and s together.

Hence  L.H.S. ≠ R.H.S.

i.e. (r + s)* = r*+s*.

Q.41 Write regular expression for the set of strings over {0, 1} that have at least one. AU: Dec.-15

Ans.: r.e. = (0*1⁺) (0+1)*

because 1⁺ = 11*. That means at least one 1 is always present in regular expression.

Q.42 State the pumping lemma for regular languages. AU: May-16, Dec.-18

Ans. Let, L be regular set. Then there is a constant n such that if z is any word in L and |z| ≥ n, we can write z = uvw such that |uv| ≤ n, |v| ≥ 1 for all i ≥ 0, then uvⁱw is in L.

Q.43 What are closure properties of regular languages. AU: Dec.-16

Ans. Following are closure properties of regular languages:

1) The union of two regular languages is regular.

2) The intersection of two regular languages is regular.

3) The complement of a regular language is regular.

4) The difference of two regular languages is regular.

Q.44 Generate NFA - ε to represent a* b|c AU: May-17

Ans.:

Q.45 Show whether a language L = {0ⁿ 1²ⁿ|n> 0} is regular or not using pumping lemma. AU: May-17

Ans.: We will map W = xyz for given string W ϵ L = {0ⁿ 1²ⁿ}

Suppose W = 001111

If we map W = xyz then -

W = 0 011 11

x = 0, y = 011 z = 11 ...(1)

By pumping lemma if W = xyⁱ z ϵ L then the language is regular.

For equation (1) we have W = xyⁱz. We assume i = 2 then string becomes

W = xyyz

= 001101111

W = 0²1² 0¹1⁴ € L

This shows that given language is not regular.

Q.46 Give language of regular expression a ? (b|c)*. AU: May-17

Ans. The ? denotes preceding character occurs for one or zero times. The * means the string occurs for any number of times. The language contains a string which may begin with single a or no a and followed by any number of b's and c's.

Q.47 Write regular expression for the set of all strings of 0's and 1's not containing 101 as substring. AU: May-18

Ans. :

r.e. = 0*(1*000*)*1*0*

In above expression all 1's are followed by 00. This pattern is repeated for any number of times.