Finite Automata & Regular Expressions - GATE CSE (CSE) Compiler Design

Explanation:
Rule (pq)*p=p (qp)*
Therefore–(xx*) (x*x**)
(xx*)(x*x*) [Using x**=x] (xx*)(x*) [Using x*x*=x*] (xx*) [Using x*xx*=x*)
x+

Explanation: The grammar itself is not regular but language L is regular as L can be represented using a regular grammar, for example S -> S00/00.

Explanation: Strings of odd number of zeroes can be generated by the regular expression (00) *0.Pumping lemma can be used to prove the non-regularity of the other options.

Explanation: Here string length is 4 so we create string of length 4 by 6 values firstly we arrange any value by 6 methods. Then Remaining numbers are 5 so we can arrange them by 5 methods then remaining numbers are 4 so we arrange them by 4 methods and then 3.Thus 6*5*4*3=360.

he FALSE statement is:

3. Context-free languages are closed under intersection.

Explanation:

• Context-free languages (CFLs) are closed under:
  • Union: If L1L_1L1​ and L2L_2L2​ are CFLs, L1∪L2L_1 \cup L_2L1​∪L2​ is also a CFL.
  • Concatenation: If L1L_1L1​ and L2L_2L2​ are CFLs, L1⋅L2L_1 \cdot L_2L1​⋅L2​ (concatenation) is also a CFL.
  • Kleene closure: If LLL is a CFL, the Kleene closure (repetition) of LLL, denoted as L∗L^*L∗, is also a CFL.

However, CFLs are not closed under intersection. The intersection of two context-free languages is not necessarily a context-free language. In fact, the intersection of two CFLs may result in a language that is not context-free.

Explanation:
S->aSbS putting S-> € and then S->SaSbS
S->aSaSaSbSbSbS putting S->SaSbS
S->aaabbb putting S->€.

Explanation: RE is used for all types of string and numbers.

Explanation: Zero or Specific Expression matching can be done only by a single character that is*

Explanation: It is seen that programmatic description are treated as regular expression.

Explanation: As per the definition of type-2 grammar.