plass-lab / formallanguages

CSE4031 Formal Languages

Hi there 👋

formallanguages's Issues

[FormalLanguages Grammar Design 질문: page 16]

※제 풀이가 잘못되었다는 반례를 찾았습니다..!

[질문 문제]
page 16: ex2) L_2={0^i 1^j | i != j, i,j>=1}
교수님께서는 해당 문제의 답으로 다음 해답을 제시해주셨었습니다.
P: S-> A|C
A-> 0A1 | 0B1
B-> 0B | 0
C-> 0C1 | 0D1
D-> 1D | 1
으로 풀어주셨습니다!

복습하는 과정에서 제가 푼 결과는 조금 다르게 나왔고 맞는 답이라고 생각이 들어서
직관적인 답이 틀려도 논리적으로 동치일 수 있는지 교수님께 여쭙고자 질문을 남깁니다.

i: i>j case)
A-> 0A1 | 0B
B-> 0B | epsilon

j: i<j case)
C-> 0C1 | D1
D-> D1 | epsilon

Therefore,

P:
S-> A | C
A-> 0A1 | 0B
B-> 0B | epsilon
C-> 0C1 | D1
D-> D1 | epsilon

이렇게 했을 경우, 주어진 Language에 해당하는 모든 문자열을 만들 수 있는것이 아닌가요?

또한, 위 생성규칙을 다음과 같이 병합해서 표현해도 무관한 것인가요?
S-> A|C
A-> 0A1 | 0A | epsilon
C-> 0C1 | C1 | epsilon

[question] Useless 생성 규칙 제거에 대해서(2018기출문제)

※6-(1) 기출 문제를 푸는 과정에서 헷갈리는 부분이 있어 질문 남깁니다.

먼저, TN집합에 해당하는 심벌들을 구했습니다.
TN={S,B,C} 따라서, NTN={A}이므로,
LHS가 A 심벌인 경우는 해당 생성 규칙 모두를 제거하였고,
RHS가 A 심벌인 경우는 A를 가진 RHS만 제거 하였습니다.

다음과 같이 생성 규칙이 남았습니다.
S->BaS | epsilon
B->cSd | a
C->cSa | epsilon

이 다음, 접근 가능한 심벌인 AS집합에 해당하는 심벌을 구하려고 하였습니다.
이때, NTN 심벌을 제거한 생성규칙에서는 C심벌에 접근할 수가 없습니다.

따라서, 헷갈렸던 점은 "NTN symbols을 제거하지 않은 상태에서 AS을 구해야하는지" or "NTN symbols을 제거한 상태에서 AS을 구하여 C 심벌을 Inaccesible Symbol로 보아야하는 것인지"에 대해서 전자가 맞다고 생각 중인데, 맞는지 확인 받고 싶습니다!``

Bracket이 빠져있음

java로 구현한 MiniScanner에서 Token과 TokenType에는 Bracket에 대한 내용이 포함되어 있지만, Scanner에는 Bracket을 인식하는 내용이 포함되어 있지 않습니다.