I need help finding the grammar of these languages. I feel like I am getting nowhere with these solution
1) {a^h b^k a^m b^n | h + k = m + n}
2) {a^i b^j a^k | (i = j and k ≥ 0) or (i ≥ 0 and j > k)}
any help would be appreciated
I assume you're looking for context-free grammars. I'll use the convention that S is the root production rule and that upper-case words are rules (like S, AB, A, etc.), the empty production is written empty and that literals are written as 'a' and 'b'.
The first grammar is:
S := AB
AB := 'a' AB 'b' | AA | BB
AA := 'a' AA 'a' | BA
BB := 'b' BB 'b' | BA
BA := 'b' BA 'a' | empty
The trick here is to realise that to keep the two halves the same length, one has to define grammar productions that add one symbol on either side. Then to note that we start by adding 'a' to the left, and 'b' to the right, and from there we proceed either adding 'a' to both sides, or 'b' to both sides, and finally proceed to adding 'b' to the left and 'a' to the right.
The second grammar is:
S := AB A | A B BA
AB := 'a' AB 'b' | empty
A := 'a' A | empty
B := 'b' B | 'b'
BA := 'b' BA 'a' | empty
This is easier than the first: the root production is already given as a choice of two things, so it's natural to express that in the rule. The first choice to to generate some number of 'a's followed by the same number of 'b's and then any number of 'a's. The second choice is to generate some number of 'a's, then some positive number of 'b's and then an equal number of 'b's and 'a's. That guarantees that "j>k" in the description of that choice.
Neither grammar here is unambiguous, although it's only a little more complicated to remove the ambiguities.