Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Easy

Regular languages and finite automata

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Finite automata are used to recognize patterns. It takes a string of symbols as input and changes the state of the string as a result. The transition takes place while the required symbol is being determined.

Regular Expressions are the expressions that define the Finite Automata language. It is the most effective way to represent any language.

Questions

1. Consider the following statements.

I. If L1∪L2 is regular, both L1 and L2 must be regular.

II. The class of regular language is closed under infinite union.

Which of the given statements is/are true?

(A) I only

(B) II only

(C) Both I and II

(D) Neither I nor II

Solution: (D) Neither I nor II

Counter examples for given statements:

I. (anbn) ∪ (a*b*) = a*b*  

where, a*b* is regular but (anbn) is not regular language.

II. Φ ∪ (ab) ∪ (a2b2) ∪ (a3b3) ..... (infinite union) = (anbn)  

where, each language in left side are regular language, but language in right side (anbn) is not regular language.

So, both statements are false.

2. For Σ = {a, b}, let us consider the regular language

L = {x ∣ x = a2 + 3k or x = b10 + 12k, k ≥ 0} 

Which of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

(A) 3

(B) 5

(C) 9

(D) 24

Solution: (D) 24

According to the Pumping lemma, there must be repetition (DFA then repeats some states, and regular grammar repeats its non-terminal in derivation.) for all acceptable stings.

Therefore, the minimum Pumping Length should be 11 because a string with length 10 (i.e., w = b10) does not repeat anything, but a string with length 11 (i.e., w = b11) will repeat states.

Therefore, the pumping length for a given language should be greater than 10, which is 24.

3. If L is considered to be a regular language over ∑ = {a, b}, which of the following languages is NOT regular?

(A) L⋅ LR {xy ⏐ x ∈ L, yR∈ L}

(B) Prefix (L) = {x ∈ ∑* ⏐ ∃y ∈ ∑* such that xy ∈ L}

(C) Suffix (L) = {y ∈ ∑* ⏐ ∃x ∈ ∑* such that xy ∈ L}

(D) {wwR ⏐ w ∈ L}

Solution: (D) {wwR ⏐ w ∈ L}

Regular languages come under reversal, concatenation, prefix(L), and suffix(L) properties. So, the languages are given in options A, B, and C is regular.

But language L = {wwR ⏐ w ∈ L}, i.e., option D is infinite and not regular because it contains string matching, and we can increase in length indefinitely, then finite automata will run out of memory, requiring a stack. Hence, it is context-free but not regular.

4. The grammar defines language L1: S1 -> aS1b | ε

The grammar defines language L2: S2 -> abS2 | ε

Consider the following statements:

P: L1 is regular

Q: L2 is regular

 

Which one of the following is TRUE?

(A) Both P and Q are true

(B) P is true, and Q is false

(C) P is false, and Q is true

(D) Both P and Q are false

Solution: (C) P is false, & Q is true.

L1 has the property that the number of a's in a string should match the number of b's and that all a's should come before all b's. As a result, extra memory will be required to check this string property (a Finite Automaton cannot be built for this language). As a result, this is not considered to be a typical language. As a result, P is False.

The feature of L2 is that the number of as should match the number of bs, however, the sequence of the as and bs is different here. It's (ab)*, which doesn't require any additional memory to accept. (For this language, a Finite Automaton can be created.) As a result, L2 is a standard language. Q is thus correct.

5. If L1 = {an|n ≥ 0} and L2 = {bn|n ≥ 0}, consider 

(I) L1⋅L2 is a regular language 

(II) L1⋅L2 = {anbn|n ≥ 0}  

Which one of the following is CORRECT? 

(A) Only I

(B) Only II

(C) Both I and II

(D) Neither I nor II

Solution: (A) Only I

L1.L2 is regular since regular languages are closed under concatenation.

But L1.L2 = {anbn | n ≥ 0} is not correct because both variable are independent of each other.

L1.L2 = {anbm | n ≥ 0 , m ≥ 0} is possible.

6. Let L1 be a recursive language and L2 and L3 be languages that are recursively enumerable but not recursive. Which one of the following assertions is not necessarily true?

(A) L2 ∪ L1 is recursively enumerable

(B) L1 – L3 is recursively enumerable

(C) L2 ∩ L1 is recursively enumerable

(D) L2 – L1 is recursively enumerable

Solution: (B) L1 – L3 is recursively enumerable

A) Always True

(Recursively enumerable - Recursive ) is 

Recursively enumerable

B) Not always true

L1 - L3 = L1 intersection ( Complement L3 )

L1 is recursive, L3 is recursively enumerable 

but not recursive Recursively enumerable languages

are NOT closed under complement.

C) and D) Always true Recursively enumerable languages 

are closed under intersection and union. 

7. Which of the following languages is described by the regular expression over the alphabet 0-1: (0+1)*0(0+1)*0(0+1)*?

(A) The set of all strings that include no more than two zeros.

(B) A collection of all strings that include the substring 00.

(C) The collection of all strings with at least two 0s.

(D) The set of all strings starts at 0 and ends at 1.

Solution: (C) The set of all strings containing at least two 0's.

Two 0′s are enclosed by (0+1)* in the regular expression, implying that approved strings must contain at least two 0′s.

The least possible string is ε 0 ε 0 ε = 00

00, 000, 100, 0010, 0000, 00100, 1001001,..... are among the allowed strings.

We can see that all of the approved strings have at least two zeros, which is the shortest length imaginable.

8. Consider the set ∑* of all strings over the alphabet ∑ = {0, 1}. ∑* with the concatenation operator for strings

(A) does not form a group

(B) forms a non-commutative group

(C) does not have a proper identity element

(D) create a group if the empty string is removed from ∑*

Solution: (A) does not form a group.

Because it follows the characteristics of Closure, Associativity, and has an identity member, the provided set with the concatenation operator creates a Monoid (null string).

It isn't a group since no element has an inverse, i.e., there does not exist string S for another string T such that T*S = null string.

9. The regular expression 0*(10*)* denotes the same set as

(A) (1*0)*1*

(B) 0 + (0 + 10)*

(C) (0 + 1)* 10(0 + 1)*

(D) none of these

Solution: (A) (1*0)*1*

There is property of regular expression (a+b)* = (a*b*)* = (a*+b*)* = (a*+b)* = a*(ba*)*= (b*a)*b*.

(1*0)*1* can generate all strings generated by the given regular expression 0*(10*)*.

10. Let L denotes the language generated by the grammar S -> 0S0/00. Which of the following is true?

(A) L = 0+

(B) L is regular but not 0+

(C) L is context-free but not regular

(D) L is not context free

Solution: (B) L is regular but not 0+

Option A: L is not 0+ since 0+ will include any arbitrary string over the alphabet 0 with any number of 0's (except empty string), for example, 0, 00, 000,00000, whereas L will only have strings like 00, 0000, 000000,..., i.e., only even numbers of 0's (excluding empty string).

Option C: L is a regular language since we can construct a regular expression for it (and create a Finite Automaton with it), which is (00)+.

Option D: L is a Context-Free Language because Grammar G, which generates the language L, is Context-Free Grammar. A Grammar G is CFG if all of its productions are of the form A->α, where A is a single non-terminal and α belongs to (V∪ T)*, i.e., α can be a string of terminals and non-terminals. (V represents a non-terminal, and T represents a terminal)

11. Let S and T be language over Σ = {a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

(A) S ⊂ T

(B) T ⊂ S

(C) S = T

(D) S ∩ T = φ

Solution: (C) S = T

Both have the same output because if we draw the DFA of S, which is (a+b*)*, at the final state, it is just repeating.

12. The string 1101 does not belong to the set represented by

(A) 110* (0+1)

(B) 1(0+1)* 101

(C) (10)* (01)* (00+11)*

(D) (00+(11)*0)*

Solution: (C) (D)

Option C's R.E will not generate 1101 because the language contains 

L(C) = Epsilon, 10, 1010, 1001, 0101, 00, 11, 0011, ...

Option D's R.E has a '1', but two' 11' are stacked together, making 1101 impossible to create.

L(D) = epsilon, 0, 00, 110, 11110, 11000, ...

13. Which of the following sets can be recognized by a Deterministic Finite-state Automaton?

(A) The numbers 1, 2, 4, 8……,2^n,………. are binary.

(B) The numbers 1, 2, 4,….., 2^n,………. are written unary.

(C) set of binary strings in which the number of ones is the same as the number of zeroes.

(D) The set {1, 101, 11011, 1110111,…….}

Solution: (A) The numbers 1, 2, 4, 8……,2^n,………. are written in binary.

If there is an infinite language, and for that language, if there is no pattern exist, then we can surely say that the given language is not regular, but if the pattern exists for that language, then it may or may not be a regular language, and if we can draw DFA for that language, it will almost certainly be regular; otherwise, it will not be regular.

Therefore option (A) is regular language as it can be written in binary, i.e.,

L = {1, 10, 100, 1000, 10000, …} 

A regular expression is (10*) since, for this expression, we can draw DFA.

14. If the regular set 'A' is defined by A= (01+1)* and the regular set 'B' is defined by B= ((01)* 1*)*, which of the following is true?

(A) B ⊂ A

(B) A ⊂ B

(C) A and B are incomparable

(D) A = B

Solution: (D) A = B

Some regular expressions are always equivalent to (0+1)* such that.

(0+1)* 

= (0*+1*)* 

= (01*)* 

= (0*+1)* 

= (0+1*)* 

= 0*(10*)* 

= 1*(01*)* 

Since,

(01+1)* = ((01)* 1* )*  

Therefore A = B.

15. Which two of the following four regular expressions are equivalent? (ε is the empty string).

(i). (00)*(ε+0)

(ii). (00)*

(iii). 0*

(iv). 0(00)*

(A) (i) and (ii)

(B) (ii) and (iii)

(C) (i) and (iii)

(D) (iii) and (iv)

Solution: (C) (i) and (iii)

Here,

(00)*(ε+0)

= (00)*.ε+ (00)*.0 

= (00)* + (00)*0 

= 0* 

It is equal to (iii) [using regular expression properties].

Here,

We see that (00)* generates strings of even length, and (00)*0 generates the strings of odd length.

16. Given ∑ = {a, b}, which of the following sets is not countable?

(A) Set all strings over ∑

(B) Set of all languages over ∑

(C) Set of all languages over ∑ accepted by Turing machines

(D) Set of all regular languages over ∑

Solution: (B) Set all languages over ∑

(A) The set ∑ ={a, b} is countable because each element of this set can be mapped with the natural number and also generated in the following order:

Given ∑ ={a, b}. So, order will be a,b,aa,ab,ba,bb,aaa,aab … Therefore it will mapped with natural number. Hence it is countable.

(B) Here, we see that a set of languages over z is the power set of strings over ∑ an infinite set, and As we know, that power set of an infinite set is uncountable. Hence the set of languages becomes an uncountable set, so we can prove this is using Cantor's diagonalization method.

(C) The set of all languages ∑ accepted by the Turing machine is countable.

(D) The set of all regular languages is a subset of all recursively enumerable languages. And we know that a subset of a countable set is always countable.

17. Let N be an NFA with n states and k be the number of states of a minimal DFA, which corresponds to N. Which one of the following is necessarily true?

(A) k ≤ n2

(B) k ≥ n

(C) k ≥ 2n

(D) k ≤ 2n

Solution: (D) k ≤ 2n

When we only have one starting state in DFA, the minimal number of states is one, and all additional states are inaccessible from the starting state.

In the worst scenario, the maximum number of states in DFA will be 2n, which is the number of subsets of a set with n elements.

Therefore, k ≤ 2n

18. Consider the following two statements:

I. If all of an NFA's states are accepting, then the NFA's accepted language is.

II. There is a regular language A such that A B is regular for all languages B.

Which one of the following is CORRECT?

(A) Only I is true

(B) Only II is true

(C) Both I and II are true

(D) Both I and II are false

Solution: (B) Only II is true

Statement I: False, Because there is no discussion of transitioning from one state to another. It is possible that there will be no specified transition between two states.

Statement II: True, Since any empty language (i.e., A = Φ ) is regular, its intersection with other languages is Φ. Thus A ∩ B is regular.

19. A deterministic finite automaton with a minimum state accepts the language L={w | w ε {0,1} *, where the number of 0s and 1s in w is divisible by 3 and 5, respectively has

(A) 15 states

(B) 11 states

(C) 10 states

(D) 9 states

Solution: (A) 15 states

Here a string w of 0's and 1's should have the property that the no of 0's in the string w should be divisible by 3 ( N(0) % 3 =0 ), and the number of 1's in the string w should be divisible by 5 (N(1) % 5 =0).

The language will contain the strings such as { ε, 000, 11111, 00011111, 00111101, 11111000, 10101011, 00000011111, …and so on }

So, strings accepted by the automaton have to be of length 0, 3, 5, 8, 11, 13, 14, 16, …and so on, i.e., an equation for length will be 3x + 5y (where x,y>=0 )

Modulo 3 gives remainder as ( 0, 1, 2 ) , and Modulo 5 gives remainder as ( 0, 1, 2, 3, 4 ). Hence 3 * 5 states, i.e., there will be 15 states in the automaton to represent this.

20. Consider the regular language L = (111 + 11111)*. Calculate the minimum number of states in any DFA accepting this language is:

(A) 3

(B) 5

(C) 8

(D) 9

Solution: (D) 9

It is given that language L = (111 + 11111)*

Strings that belongs in the language are

L = {null , 111 , 11111, 111111 , 11111111 , 111111111 , 1111111111 , ……. form string length 8 , (number of 1’s) , now we can can generate any length of string from length 3 and 5 (i.e. length 8 ,length 9, length 10 , length 11 ,…etc)}

L = {null , 111 , 11111, 111111 , 11111111 , 111111111* }

Strings in length , that belongs in the language

L = {0 ,3, 5, 6, 8, 9, 10, 11, …}

So, 5 states are final states, and 4 states are non-final states

Therefore the total number of states is 9.

21. The following finite state machine accepts all those binary strings in which the number of 1's and 0's are, respectively.

(A) divisible by 3 and 2

(B) odd and even

(C) even and odd

(D) divisible by 2 and 3

Solution: (A) divisible by 3 and 2

Option (B) is eliminated because string 100 contains an odd number of 1s and even a number of 0s which the DFA does not accept.

Option(C) is eliminated because string 011 contains an even number of 1s and an odd number of 0s which the DFA does not accept.

Option (D) is eliminated because string 11000 has a number of 1s divisible by 2 and a number of 0s divisible by 3 which the DFA does not accept.

Option (A) accepts all strings with the number of 1s divisible by 3 and the number of 0s divisible by 2.

22. Consider the following deterministic finite-state automaton M.

Let S denote the set of seven-bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that M accepts is

(A) 1

(B) 5

(C) 7

(D) 8

Solution: (C) 7

You are given a language of 7-bit strings where 1st, 4th, and 7th bits are 1.

The following are seven language strings that DFA will accept:

1001001

1001011

1001101

1001111

1101001

1111001

1011001

23. Consider a DFA over ∑ = {a, b} accepting all strings which have the number of b's divisible by 8 and number of a's divisible by 6. Calculate the minimum number of states that the DFA will have?

(A) 8

(B) 14

(C) 15

(D) 48

Solution: (D) 48

For strings divisible by 8, we create a DFA.

It necessitates a minimum of 8 states as string length mod 8 = 0, 1, 2, 3, 4, 5, 6, 7

For strings divisible by 6, we create a DFA.

It necessitates a minimum of 6 states as string length mod 6 = 0, 1, 2, 3, 4, 5.

If the first DFA is minimum and the second DFA is also minimum, after merging both DFAs resultant DFA will also be minimum. Such DFA is called compound automata.

So, the minimum states in the resultant DFA will be 6 * 8 = 48

Check out this article - Converting NFA to DFA

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

  1. Is it possible to use null values in DFA?
    No, it is not possible to use the null values in DFA.
  2. In DFA, how many pathways are there to move from one state to another for a given input?
    In DFA, there can only be one path for specific input from one state to the next.
  3. What does Φ signify in a regular expression?
    In a regular expression, Φ symbol signifies an empty set.

Key Takeaways

In this article, we have discussed the Regular languages and finite Automata of previous year's questions. We hope that this blog will help you understand the questions based on the Regular languages and finite automata in competitive GATE exams, and if you would like to learn more about Regular languages and finite automata, check out our other articles on Regular languages and finite automata.

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Topics covered
1.
Introduction
2.
Questions
2.1.
Solution: (D) Neither I nor II
2.2.
Solution: (D) 24
2.3.
Solution: (D) {wwR ⏐ w ∈ L}
2.4.
Solution: (C) P is false, & Q is true.
2.5.
Solution: (A) Only I
2.6.
Solution: (B) L1 – L3 is recursively enumerable
2.7.
Solution: (C) The set of all strings containing at least two 0's.
2.8.
Solution: (A) does not form a group.
2.9.
Solution: (A) (1*0)*1*
2.10.
Solution: (B) L is regular but not 0+
2.11.
Solution: (C) S = T
2.12.
Solution: (C) (D)
2.13.
Solution: (A) The numbers 1, 2, 4, 8……,2^n,………. are written in binary.
2.14.
Solution: (D) A = B
2.15.
Solution: (C) (i) and (iii)
2.16.
Solution: (B) Set all languages over ∑
2.17.
Solution: (D) k ≤ 2n
2.18.
Solution: (B) Only II is true
2.19.
Solution: (A) 15 states
2.20.
Solution: (D) 9
2.21.
Solution: (A) divisible by 3 and 2
2.22.
Solution: (C) 7
2.23.
Solution: (D) 48
3.
FAQs
4.
Key Takeaways