GATE Computer Science Engineering(CSE) 2027 Test: Regular Expressions

A language is known as regular language if there exists a finite automaton (no matter whether it is deterministic or non-deterministic) which recognizes it. So if for a given language, we can come up with an finite automaton, we can say that the language is regular. But sometimes, it is not quite obvious to design an automaton corresponding to a given language but it surely exists. In that case, we should not start thinking that the given language is not regular. We should use pumping lemma to decide whether the given language is regular or not.
According to pumping lemma, “Suppose L is a regular language, then there exists a l ≥ 1 such that for all string s ∈ L, where |s| ≥ l, we can always split s (there exists at least one such splitting) in such a way that s can be written as xyz with |xy| ≤ l and y ≠ ε  and for all i ≥ 0 , xyⁱz ∈ L”. l is known as pumping length. Let’s rephrase the given Lemma for non regular languages. Suppose L is a language, if for all l ≥ 1 there exist a string s ∈ L with |s| ≥ l such that for all splitting (there doesn’t exists a single splitting which doesn’t follow this rule) of s in form of xyz such that |xy| ≥ l and y ≠ ε , there exists an i≥ 0 such that xyⁱz ∉ L, then L is not regular. Notice that here we stress on finding such s if we want to prove that a language is not regular.
Choice of the Questions:
(a) In choice 1, Lets first consider w being of length n and containing only a. In this case the language represents aⁿaⁿ. The length of the string represented by language should be Even. Consider l = n, then xyz = aⁿaⁿ with xy = aⁿ. lets assume y = a, then consider the membership of xyⁱz with i = 0. This will simply be of odd length which doesn’t belongs to L. So L is not regular. To discuss it in more detail, let’s consider another example. Suppose w = a^pb, then string formed by L will be a^pba^pb which is of length 2p + 2. Assume l = p, then xy = a^p. suppose y = a, then consider the membership of xyⁱz with i = 0. This certainly doesn’t belongs to L. So L is not regular.
(b) In choice 2, The first example will work as above. In the second example, the string will be a^pbba^p, and there will be no changes in process for proving it to be non regular.
(c) In choice 3, Assuming that we are considering integer from 0 and 0^2∗n results in empty string, Which is also accepted, We can simply construct a DFA as given below. It simply accepts a string if it is either empty or contain even number of zeros. So the language is regular.

(d) In choice 4, We can simply assume that the pumping length l =i²/2. Now consider the xy = 0^l with y = 0, Now if we check the membership of xy²z, we can find that this will represent 0^{i^2}+1, and corresponding to which there exists no j such that j² = i² + 1 where i and j are integer except j = 1 and i = 0. But since i can’t be zero. In Short, using pumping lemma, we can generate 0^{i^2}+1 as well as 0^{i^2}-1, which won’t be available in L. So L is not regular.

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

Option A : L is not 0+ , because 0+ will contain any arbitrary string over alphabet 0 with any no of 0's ( except empty string ), for ex: {0, 00, 000,00000}, but L will only have the strings as { 00, 0000, 000000,...}, i.e only even no of  0's ( excluding empty string}.  Option D : L is a Context Free Language, because the 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/or Non-terminals. (V represents a non-terminal and T represents a terminal) Option C : L is a Regular Language, Because we are able to write a regular expression for it ( and also able to make a Finite Automaton), which is (00)+.Option B :  Hence This option is Correct, because L is Regular but not 0+, as we proved above

There are two states. When first state is final, it accepts even no. of a's. When second state is final, it accepts odd no. of a's.

To reach the accepting state, any string will have to go through edges having aababb as labels in order. Though it might not be a continuous substring, but it sure will be a substring. There might be some cases where same substring always exists as a prefix or suffix for some DFA, but in this situation we don’t have to consider those cases, given this question has single choice answer. − > O − a− > O − a− > O − b− > O − a− > O − b− > O − b− > O Hence, correct answer should be (B).

In DFA M: all strings must end with 'a'. In DFA N: all strings must end with 'b'. So the intersection is empty. For an empty language, only one state is required in DFA. The state is non-accepting and remains on itself for all characters of alphabet.

The smallest possible string by given grammar is "11". X0 = 1X1
= 11X2 [Replacing X1 with 1X2]
= 11 [Replacing X2 with λ]
The string "11" is only possible with option (C).

L3 is simple to guess, it is regular. Below is DFA for L1.

L1 is interesting. The important thing to note about L1 is length of x is greater than 0, i.e., |x| > 0.
So any string than starts and ends with same character is acceptable by language and remaining string becomes w. Below is DFA for L1.

Below is NFA for the given regular expression (0 + 1)*(10)

Below is DFA for the same. 

The given regular expression matches with all strings that contain 0011. The complement should match with all strings except the strings with 0011 as substring. Following are some interesting facts/observations from this question.
1) Complement of a regular language is also regular.
2) Since complement is regular, it is always possible to make a DFA for complement.
3) A DFA that accepts its complement is obtained from the above DFA by changing all non-accepting states to accepting states and vice versa as done in this question. Below is DFA for the complement. We can get below DFA by first drawing DFA of regular language for strings with substring as 0011. After drawing DFA, we can invert all states (single circle to double circle and vice versa)

C- (ab)* + c*)* will always give strings with "ab" together.Whereas (a+b+c)* would generate language where a,b,c may not be always together. A,B,D may generate same language as (a+b+c)*   So, Answer is (C)

Basics of PDA A push down automata or a PDA is essentially a NFA with a stack and its transition function also depends on the symbol at the stack top. Formally, a PDA is a 6-tuple (Q, Σ, Γ, δ, q0, F) with Q being set of all possible states, Σ is the set of all possible input, Γ is the set of all possible stack symbol, δ : Q × Σ × Γ → Q × Γ is the transition function, q0 is the initial state, and F ⊆ Q is the set of final state. Some times, PDA is also known to be of 7 tuples when we considers the initial stack symbol z0 as an additional member in the above 6 tuples. Note that there should exists a transition function for a given input otherwise there won’t be any possible move. The PDA can be of two types: Empty stack accepting PDA and Final state PDA. Empty stack accepting PDAs are the PDAs for which a given input is accepted if on a given input string, when the input exhausts, the stack should be empty. Similarly, a Final state accepting PDA is a PDA for which a given input is accepted if on a given input string, when the input exhausts, thePDA should be in one of the final states. A Non-deterministic PDA or NPDA is a PDA in which, for a given input, multiple output is possible. i.e. The Transition function δ maps a given input from Q × Σ × Γ to a finite set of Q × Γ. For the given question, since there is a more than one output corresponding to a given input for transition function, we will consider a NPDA for the execution of the input and we will halt our execution for a corresponding branch if there is no move possible for a given input and We assume that if the machine halts at one of the final state and input is exhausted, we accept the string otherwise we reject it. Notice, the Given PDA is final state accepting PDA and not the empty stack accepting PDA. Choice of the Questions:  We will assume the initial stack symbol is ε, and
• In choice 1, The execution will be as follow: (s, a, ) → (s, a) or (f, ε). Let’s first consider, (s, a) as output and execute the remaining input. (s,a, a) → No valid Move. halt this branch and not in the final state, so not accepted. Now consider (f, ε) as output. (f, a, ε) → No Valid Move. halt this branch Notice that the PDA is in one of the final state, But the input string is not exhausted, So this should not be accepted by the PDA.
• In choice 2, The Execution will start as of choice 1 and will halt at character 2 as no possible move. This option is also not accepted in same way as of the first option. 3
• In choice 3, The execution will be as follow: (s, b, ε) → (s, a). (s, a, a) → No Possible move. halt this branch. Since halted before reaching to any final state so this option is not accepted.
• In choice 4, This option is also not accepted as the PDA will halt at second character as it halted in previous option. This option is also not accepted.   Assuming that if the PDA halts on a input due to no possible move and if the current state is one of the final state but the input is not exhausted, PDA will reject that string, For Question 2, Every answer is true i.e. None of the given for string belongs to the given PDA’s language. Again, Assuming that if the PDA halts on a input due to no possible move and if the current state is one of the final state but the input is not exhausted, the PDA will keep on consuming the input string until the end of string comes, string in option (A) and option (B) will be accepted by the language of this PDA. while option (C) and option (D) still won’t get accepted as by the end of the string, the PDA won’t be in final state. So keeping this assumption in mind, option (C) and option (D) both will be true for this question.

Proposition: L is a regular language M is a context free language Derivation: L_c  union M_c = complement{L intersection M} Now, L intersection M is a CFL according to closure laws of CFLs, i.e. intersection of a CFL with RL is always a CFL. But, complement{L intersection M} might not be a CFL because complement over CFL doesn't guarantee a CFL. It can even be a RL or it might even lie outside the CFL circle. It will be a context-sensitive language certainly, but nothing else can be said about it. Conclusion: Considering the above derivation, none of the statements are true. Hence correct answer would be (D) None of the above.

First of all, A string can never be infinite because String is a finite sequence of symbols over Σ So option (c) and (d) are eliminated. And because of star(*) it can generate infinite set. So Option (B) is CORRECT. 

The value of ‘n’ is finite. So, only finite number of strings can be part of given language. Therefore, we can construct a finite state automata for this language. 
 
Thus, option (A) is correct. 
 
Please comment below if you find anything wrong in the above post.

A generic approach to solve such questions would be to come up with the corresponding regular languages and compare the two. Ardens theorem could be used to achieve the objective. Moreover, some conclusions could be drawn without even deriving the languages completely, solely from the intermediary equations. Constructing equations for every state -: X = Z0 +X1, Y = X0 +Y0 +Z0 && Z = X0 + Y1 + Z1. Clearly, regular languages L1 and L2 couldn’t be same. Now, to check which of the other three options are correct, we need to find : 1) a string which is accepted by L1 but not by L2. 2) a string which is accepted by L2 but not by L1. If there exists string 1) but not 2) then L2 ⊂ L1 and likewise. Trying our hands at the given DFA, 1) string 00 is accepted by L1 but not by L2 and 2) string 01 is accepted by L2 but not by L1. Hence, neither of the two languages our subset of the other.

L1 can have 00 string while L2 can't. L2 can have 01 while L1 can't None of them can be either equal or proper subset of each other.So Ans. D.

Pumping lemma is negativity test. We use it to disprove that a languages is not regular. But reverse is not true.

According to leftmost derivation : 
E -> E + E (using E -> E + E) E -> E + E + E (using E -> E + E) E -> E + E + E + E (using E -> E + id) E -> id + E + E + E (using E -> id) E -> id + id + E + E (using E -> id) E -> id + id + id + E (using E -> id) E -> id + id + id + id 
 
According to rightmost derivation : 
E -> E + E (using E -> E + E) E -> E + E + E (using E -> E + E) E -> E + E + E + E (using E -> E + id) E -> E + E + E + id (using E -> id) E -> E + E + id + id (using E -> id) E -> E + id + id + E (using E -> id) E -> id + id + id + id 
 
Thus, option (A) is correct. 
 
Please comment below if you find anything wrong in the above post.

Background Required to solve the question - Parse Tree Construction.

Explanation : In order to produce the yield id + id + id + id , we only required 3 productions of type E → E + E as 3 ‘+’ are required in the final string. This can be done in 5 ways as shown in the picture given below: