Gate Bits FA and RE 1

In this class, We discuss Gate Bits FA and RE 1.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of finite automata and regular expressions. Click Here.

Example 1:

Gate 2001:

Consider the following two statements:

Which of the following is correct?

(A) Only S1 is correct

(B) Only S2 is correct

(C) Both S1 and S2 are correct

(D) None of S1 and S2 is correct

Statement 1 is correct. We designed finite automata for the language given in statement 1. Click Here.

Statement 2 is wrong. We can not write finite automata for the language given in statement 2. Click Here.

Solution: A

Example 2:

Gate 2009

Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)* ?

(A) The set of all strings containing the substring 00.

(B) The set of all strings containing at most two 0’s.

(C) The set of all strings containing at least two 0’s.

(D) The set of all strings begins and ends with 0 or 1.

Solution: C

The basics to solve the bit. Click Here.

Example 3:

Gate 2012:

What is the complement of the language accepted by the NFA shown below?Assume Σ={a}Σ={a} and ϵ is the empty string.

(A) ϕ

(B) {ϵ}

(D) {a,ϵ}

Solution: B

L complement is Σ* – L. We get epsilon.

Example 4:

Gate 2013:

Consider the languages L1 = Φ and L2 = {a}. Which one of the following represents L1 L2* U L1*

(A) {ϵ}

(B) ϕ

(D) {a,ϵ}

Solution: A

Check the identity rules of regular expressions. Click Here.

ϕ a* + ϕ*

ϕ + ϵ

{ϵ}