Language and Grammar


Q. Define symbol, alphabet and string.

Ans. Symbol: A symbol is a user-defined entity.

Alphabet: An alphabet is a finite set of symbols denoted by Σ in automata. Alphabets are a set of symbols used to construct a language. Example, {0, 1} is binary alphabet, {A…, Z, a…z} is the alphabet set for the English language.

String: A string is defined as a sequence of symbols of finite length. A string is denoted by w in automata. Example, 000111 is a binary string.

(Length of a string w is denoted by |w|. For the previous case, |w| = |000111| = 6).

Q. Define Prefix, proper Prefix, Suffix, proper Suffix, and substring in relation to a string.

Ans. Prefix: The prefix of a string is the string ...

Get Express Learning: Automata Theory and Formal Languages now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.