Question

Give examples of when each of the following are useful?

a) Regular language

b)Context Free Language

c)NP-Completeness

d)Decidability

Answer 1

Step-by-step 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