Question

Give examples of when each of the following are useful?

Answer 1

Explanation:

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