The Gateway to Computer Science Excellence

+4 votes

Which of the following grammars generate regular language?

a. S $\rightarrow$ aSa | bSb | a

b. S $\rightarrow$ aS | bS | aA | bA

A $\rightarrow$ bAc | $\epsilon$

c. S $\rightarrow$ aA | $\epsilon$

A $\rightarrow$ Sb

d. None of these

Why (A) is not regular? as {WCW^r | W,C belongs to (a,b)} is regular}

+2 votes

Best answer

0

Yes, when that intermediate symbol belongs to the alphabet, then it should be a regular language.. https://gateoverflow.in/12374/gateoverflow.in

+1

X in the example in mentioned link , is not just a symbol, from that X we can generate all strings as there X $\in \{a,b\}^*$ .

0 votes

As a rule of thumb, the production rules for type-3 grammar are restricted to following two types :

- $X \rightarrow a$
- $X \rightarrow a Y$

where $X$ and $Y$ are variables, and $a$ is terminal.

Hence, the correct option is D.

Refer this link for more details.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,700 answers

199,396 comments

107,474 users