Give examples of when each of the following are useful?

a) Regular language

b) Context Free Language

c) NP-Completeness

d) Decidability

a. Regular language -

Uses are as follows -

matching the regular expression patterns, like the Unix grep. patterns search and replace operations. programming languages for the Lexical analysis in the compilation phase.

b. Context Free Language -

Uses are as follows -

match the count of one symbol with another symbol. Match a symbol with another symbol. submit one symbol with string made of other symbols recursively.

c. NP-Completeness -

Uses are as follows -

used for Weighted Model Counting Used for Integer Programming used for Boolean Satisfiability testing

d. Decidability -

Uses are as follows -

Team games with incomplete information are undecidable. Infinite chess (with limitations on rules and game pieces) is decidable. Chess is decidable game