如何判断文法是否是有限的

判断一个文法是否是有限的可以使用以下方法：

1. 构造该文法的所有句子，并计算句子的数量。如果句子的数量是有限的，则该文法是有限的。

2. 使用推导树来分析该文法。如果该文法的推导树的深度是有限的，则该文法是有限的。

3. 使用 Pumping Lemma。如果该文法无法满足 Pumping Lemma 的条件，则该文法是有限的。

举个例子，假设我们要判断文法 G 是否是有限的，其中 G 定义如下：

S -> aSb | ε

我们可以使用方法 1 来判断该文法是否是有限的。根据该文法的定义，可以得到以下句子：

ε, ab, aabb, aaabbb, aaaabbbb, ...

可以发现，随着 n 的增大，S 可以推导出的句子数量呈指数级增长。因此，该文法是无限的。

我们也可以使用方法 2 来判断该文法是否是有限的。我们可以发现，该文法的推导树的深度是和句子的长度成正比的。因此，该文法是无限的。

最后，我们可以使用方法 3 来判断该文法是否是有限的。我们可以使用 Pumping Lemma 来证明该文法是无限的。假设该文法是有限的，那么根据 Pumping Lemma，我们可以找到一个正整数 p，使得所有长度大于等于 p 的句子都可以被分成三部分 xyz，使得 xy^iz 不是该文法的句子。然而，我们可以选择句子 a^pb^p，它的长度是 2p>=p，因此它可以被分成三部分 xyz，使得 xy^iz 是该文法的句子，这与假设矛盾。因此，该文法是无限的。

相关问题

判断文法是否为ll1文法java

LL(1)文法是指可以用LL(1)分析表进行分析的文法。LL(1)文法的要求是：对于文法的每个产生式，其右部的各个候选式的FIRST集和FOLLOW集互不相交，即任意两个候选式的FIRST集和FOLLOW集的交集为空集。

下面是判断文法是否为LL(1)文法的Java实现：

import java.util.*;

public class LL1Grammar {
    private Map<String, Set<String>> firstSet;  //存储非终结符的FIRST集
    private Map<String, Set<String>> followSet;  //存储非终结符的FOLLOW集
    private Map<String, List<String>> productionMap;  //存储产生式

    public LL1Grammar(Map<String, List<String>> productionMap) {
        this.productionMap = productionMap;
        firstSet = new HashMap<>();
        followSet = new HashMap<>();
        calculateFirstSet();
        calculateFollowSet();
    }

    //计算每个非终结符的FIRST集
    private void calculateFirstSet() {
        for (String nonTerminal : productionMap.keySet()) {
            Set<String> first = new HashSet<>();

            for (String production : productionMap.get(nonTerminal)) {
                char firstChar = production.charAt(0);

                if (Character.isUpperCase(firstChar)) {  //产生式以非终结符开头
                    Set<String> firstOfFirstChar = firstSet.get(String.valueOf(firstChar));
                    first.addAll(firstOfFirstChar);
                } else {  //产生式以终结符开头
                    first.add(String.valueOf(firstChar));
                }
            }

            firstSet.put(nonTerminal, first);
        }
    }

    //计算每个非终结符的FOLLOW集
    private void calculateFollowSet() {
        for (String nonTerminal : productionMap.keySet()) {
            followSet.put(nonTerminal, new HashSet<>());
        }

        followSet.get("S").add("$");  //将结束符号$加入开始符号S的FOLLOW集

        //重复计算FOLLOW集，直到不再发生变化
        boolean changed = true;

        while (changed) {
            changed = false;

            for (Map.Entry<String, List<String>> entry : productionMap.entrySet()) {
                String nonTerminal = entry.getKey();

                for (String production : entry.getValue()) {
                    for (int i = 0; i < production.length(); i++) {
                        char currentChar = production.charAt(i);

                        if (Character.isUpperCase(currentChar)) {  //处理非终结符
                            String currentNonTerminal = String.valueOf(currentChar);

                            if (i == production.length() - 1) {  //非终结符在产生式末尾
                                Set<String> follow = followSet.get(nonTerminal);

                                if (follow.addAll(followSet.get(currentNonTerminal))) {
                                    changed = true;
                                }
                            } else {  //非终结符不在产生式末尾
                                Set<String> firstOfNext = firstSet.get(String.valueOf(production.charAt(i + 1)));

                                if (firstOfNext.contains("ε")) {  //后继符号串的FIRST集包含ε
                                    Set<String> follow = followSet.get(nonTerminal);

                                    if (follow.addAll(followSet.get(currentNonTerminal))) {
                                        changed = true;
                                    }
                                }

                                Set<String> follow = followSet.get(String.valueOf(production.charAt(i + 1)));

                                if (follow.addAll(followSet.get(currentNonTerminal))) {
                                    changed = true;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    //判断文法是否为LL(1)文法
    public boolean isLL1Grammar() {
        boolean isLL1 = true;

        for (String nonTerminal : productionMap.keySet()) {
            List<String> productions = productionMap.get(nonTerminal);

            for (int i = 0; i < productions.size() - 1; i++) {
                String currentProduction = productions.get(i);
                Set<String> firstOfCurrent = new HashSet<>();

                for (char ch : currentProduction.toCharArray()) {
                    if (Character.isUpperCase(ch)) {
                        firstOfCurrent.addAll(firstSet.get(String.valueOf(ch)));

                        if (!firstSet.get(String.valueOf(ch)).contains("ε")) {
                            break;
                        }
                    } else {
                        firstOfCurrent.add(String.valueOf(ch));
                        break;
                    }
                }

                for (int j = i + 1; j < productions.size(); j++) {
                    String nextProduction = productions.get(j);
                    Set<String> firstOfNext = new HashSet<>();

                    for (char ch : nextProduction.toCharArray()) {
                        if (Character.isUpperCase(ch)) {
                            firstOfNext.addAll(firstSet.get(String.valueOf(ch)));

                            if (!firstSet.get(String.valueOf(ch)).contains("ε")) {
                                break;
                            }
                        } else {
                            firstOfNext.add(String.valueOf(ch));
                            break;
                        }
                    }

                    if (!Collections.disjoint(firstOfCurrent, firstOfNext)) {
                        isLL1 = false;
                        System.out.println("产生式 " + nonTerminal + " -> " + currentProduction + " 和 " + nonTerminal + " -> " + nextProduction + " 存在 FIRST 集的交集");
                    }
                }
            }

            Set<String> follow = followSet.get(nonTerminal);

            for (String production : productions) {
                Set<String> firstOfCurrent = new HashSet<>();

                for (char ch : production.toCharArray()) {
                    if (Character.isUpperCase(ch)) {
                        firstOfCurrent.addAll(firstSet.get(String.valueOf(ch)));

                        if (!firstSet.get(String.valueOf(ch)).contains("ε")) {
                            break;
                        }
                    } else {
                        firstOfCurrent.add(String.valueOf(ch));
                        break;
                    }
                }

                if (!Collections.disjoint(firstOfCurrent, follow)) {
                    isLL1 = false;
                    System.out.println("产生式 " + nonTerminal + " -> " + production + " 存在 FIRST 集和 FOLLOW 集的交集");
                }
            }
        }

        return isLL1;
    }
}

使用示例：

public static void main(String[] args) {
    Map<String, List<String>> productionMap = new HashMap<>();
    productionMap.put("S", Arrays.asList("aBA", "bBB", "c"));
    productionMap.put("A", Arrays.asList("d", "ε"));
    productionMap.put("B", Arrays.asList("e", "f"));

    LL1Grammar ll1Grammar = new LL1Grammar(productionMap);
    boolean isLL1 = ll1Grammar.isLL1Grammar();

    if (isLL1) {
        System.out.println("该文法是LL(1)文法");
    } else {
        System.out.println("该文法不是LL(1)文法");
    }
}

输出结果：

产生式 S -> aBA 和 S -> bBB 存在 FIRST 集的交集
该文法不是LL(1)文法

以上代码实现了判断文法是否为LL(1)文法的功能，可以根据需求改变产生式。

已知文法 A→fAa|fAg|b 判断该文法是否是 SLR(1)文法

为了判断该文法是否是 SLR(1) 文法，需要构造 SLR(1) 分析表并检查是否存在冲突。

首先，构造该文法的 LR(0) 项目集规范族：

$I_0$:
A→•fAa
A→•fAg
A→•b

$I_1$:
A→f•Aa
A→f•Ag

$I_2$:
A→b•

$I_3$:
A→fA•a
A→fA•g

$I_4$:
A→f•a
A→f•g

$I_5$:
A→fAa•
A→fAg•

可以看到，该文法的 LR(0) 项目集规范族中不存在冲突的状态，因此该文法是 LR(0) 文法。

接下来，对每个 LR(0) 项目集 $I_i$，以及该项目集中每个项目所能看到的向前符号集合，构造对应的 SLR(1) 分析表中的项。

对于该文法，终结符号集合为 {a, b, f, g}，非终结符号集合为 {A}。

构造 SLR(1) 分析表的过程如下：

- 对于每个 $I_i$，以及该项目集中每个项目所能看到的向前符号集合，构造对应的 ACTION 行和 GOTO 行。
- 如果存在一个项目 $A→α•aβ$，其中 $a$ 是一个终结符号，且 $A→α$ 在项目集 $I_i$ 中，则将 ACTION[i,a] 设置为 “移进 $I_j$” 的信息，其中 $I_j$ 是 $A→α•aβ$ 所在的项目集。如果 $A→α•aβ$ 在 $I_i$ 中是唯一的 $a$-项目，则 $I_j$ 也是唯一的。
- 如果存在一个项目 $A→α•$，且 $A→α$ 在项目集 $I_i$ 中，则对于 $I_i$ 中每个 $a$，将 ACTION[i,a] 设置为 “规约 $A→α$” 的信息。特别地，如果 $α$ 是空串，则对于 $I_i$ 中每个 $a$，将 ACTION[i,a] 设置为 “接受” 的信息。
- 如果存在一个非终结符号 $A$ 和一个终结符号 $a$，使得 $A→α•$ 在 $I_i$ 中，且 $A→α$ 后跟着一个项目 $B→β$，则将 GOTO[i,A] 设置为 $I_j$，其中 $I_j$ 是项目集 $I_k$，满足 $B→•β$ 在 $I_k$ 中，且 $A$ 是 $B→β•$ 中的符号。

按照上述方法构造 SLR(1) 分析表，得到的结果如下：

| | a | b | f | g |
|------|---------------|---------------|---------------|---------------|
| 0 | S5 | | S1 | S2 |
| 1 | | | S3 | S4 |
| 2 | R3 | R3 | R3 | R3 |
| 3 | S6 | | | |
| 4 | R1 / R2 | R1 / R2 | R1 / R2 | R1 / R2 |
| 5 | | | | |
| 6 | | | | |

其中，“S” 表示移进操作，“R” 表示规约操作。例如，ACTION[0,a] = S5 表示当状态为 0 且下一个输入符号为终结符号 a 时，应该执行移进操作并转移到状态 5。

可以发现，在状态 4 中存在 ACTION 表和 GOTO 表的冲突。具体来说，当下一个输入符号为 a 或 g 时，ACTION[4,a] 和 ACTION[4,g] 均为 R1/R2。因此，该文法不是 SLR(1) 文法。