I have a homework set that i have been working on for awhile here and there are a couple questions i had to skip over because i was totally clueless and couldn't find any info in the book or on google

it may look semi long but there are really only 3 questions here...

if anyone could help me out or point me in the right direction, it would be much appreciated...even if you only kinda know or might have a slight bit of input, it would be appreciated

1. True or false with formal justification: The problem A belongs to the NP complexity class so an efficient algorithm for A exists

2. L = {w[size=-1]∈Σ* | where each opening symbol, "[, <", has a matching closing symbol, "], >"} and Σ* = {[, <, a, >, ]}. The string []aa<a[a]> is an element of L while the string <<a<<[] is not.

<b>Descrete Math:

I. BASE

1 L = (NULL STRING)

2 L = {[,]}

3 L = {<,>}

4 L = {a}

II. RECURSIVE

1) FROM I L = (NULLSTRING)

2) FROM I2 & 1 L = [](NULLSTRING)

.... and so forth keep the pattern going then u can compair the recursive pattern

III. RESTRICTION

ALL ELEMENTS IN Σ are productions of I and II only.

Classify the language L as tightly as possible using formal techniques.

a) To show that a language is regular, construct a DFA or regular expression and you are done.

b) To show that a language is CF, construct a PDA or CFG and then show that the language is not regular.

c) To show that a language is Recursive, construct a deciding TM and then show that the language is not CF.

d) To show that the language is RE construct an accepting TM and reduce the language to an undecidable language.

e) To show that the language is co-RE reduce to a co-RE language.

3. Given the sextuple of language classes, (R, CF, Recursive, RE, P, NP) then every language can be associated with a binary sextuple where symbol 1 denotes membership and symbol 0 denotes non-membership. For example, if the language were in the first calss and not in any others, it would be associated with (1, 0, 0, 0, 0, 0). State the binary sextuple associated with each of the following languages.

a) L = {a, aa, ab}

b) L = {w[/size][size=-1]∈{a, b}* | where |w| is odd and w contains exactly one b in the center of the word}

c) L = {w[/size][size=-1]∈{a, b}* | where |w| is odd and w contains exactly one b}

d) L = {The language of chess board configurations where white can win}

e) L = {The language of graphs that have a tour where each vertex is visited exactly once}

f) State three binary sextuplets that cannot exist and indicate where the contradiction occurs in each case

once again, any help on any of these questions would be greatly appreciated

thanks in advance

[/size]

Click to expand...