Register

Grammar

2,766 views
1 1 vote
Can set of terminal be empty in a grammar?

Is epsilon (null string) counted as a terminal symbol?

2 Answers

Best answer
2 2 votes
Set of terminals should be non-empty and finite.
And epsilon is not a terminal symbol.
• selected by
1 1 vote

Can set of terminal be empty in a grammar?

As per Ullman,

Terminal is a finite set of symbols that forms the string of the language being defined.

for a language,  L = { }, terminal set will be empty. 

Is epsilon (null string) counted as a terminal symbol?

The null string is not a terminal symbol. A terminal symbol is an element of the alphabet, but the empty string is not an element of the alphabet. Alphabet contain atomic symbols of length 1, but epsilon is of length 0.

 

Voting & Accepting an answer helps improve the community
← Previous · ME testNext → · array in cache
← Previous in category · draw DFA of all stri...Next in category → · Turing machine
Position:
Show:

Related questions

0 0 votes
1 1 answer
22
22 views
GO Classes asked 20 hours ago
22 views
GO Classes DPP | GATE CS | Theory of Computation | Grammar Classification
Consider the grammar $$S\rightarrow aS\mid Sb\mid b$$ Which of the following statements are correct?The given grammar is a Type $3$ grammar. The given grammar is a Type $...
2 2 votes
1 1 answer
85
85 views
GO Classes asked Sep 5
85 views
GO Classes DPP | GATE CS | Theory of Computation | NFA to Grammar
Consider the NFA given below: Which right-linear grammar is obtained by the standard NFA-to-grammar construction?$q_0 \to aq_1$,$q_1 \to aq_0 \mid bq_1 \mid \epsilon$ $q_...
1 1 vote
1 1 answer
104
104 views
GO Classes asked Sep 5
104 views
GO Classes DPP | GATE CS | Theory of Computation | Grammar to NFA
Consider the right-linear grammar,$$\begin{aligned}S &\to aB \mid bS \mid \epsilon \\B &\to aS \mid bB\end{aligned}$$Which NFA is obtained by the standard grammar-to-NFA ...
3 3 votes
1 1 answer
150
150 views
GO Classes asked Sep 5
150 views
GO Classes DPP | GATE CS | Theory of Computation | Grammar to NFA
Consider the right-linear grammar,$$\begin{aligned}S &\to aT \\T &\to abcS \mid b\end{aligned}$$If this grammar is converted into an NFA with one input symbol per transit...